--- tags: 圖論 title: BFS & DFS --- :::info [給個玩具](https://domen111.github.io/Draw-Graph/) [先備知識](https://hackmd.io/E4QVDYwYQoislArM7TqA8g) [queue用法](https://emanlaicepsa.github.io/2020/12/03/0-19/) ::: # BFS ## 圖的走訪 :::info 給定一張圖，要怎麼樣歷遍所有點或找尋兩點路徑? $範例由1開始至4$ ![](https://i.imgur.com/c9Vux3i.png) ::: :::success 我們可以由 $1$ 號點開始，每次走訪該點附近尚未走訪的點 並將走訪過的點丟入一個 $Queue$ 裡面 如此反覆循環，直至走到目標點為止 時間複雜度： $O(E)$ $E$ 為圖的點數，一次歷遍 ::: :::warning 走訪小技巧 開一個 $vis$ 陣列，將走訪過的點標記 避免再次尋訪浪費時間 (視題目做標記) ```c++= vis[100005] = {}; vis[i] = 1; //代表一號點走過 ``` ::: ## 迷宮問題 請先看 Zero Judge d453 $000000$ $011101$ $000010$ $011000$ $000010$ :::info 起點在第一行第三列 (直行橫列) 因為 $a[3][1]$ 同理終點第四行第三列 ::: :::success 我們可以建一個陣列，表示走路方向 ```c++= // version 1 int dir[4][2] = { {0,1}, {1,0}, {0,-1}, {-1,0}, }; // version 2 int dx[5] = {0,1,0,-1}; int dy[5] = {1,0,-1,0}; ``` 然後針對當前座標 找尋他四周可不可以走，如果可以就一直走訪 然後丟入 $Queue$ 直至終點或無法走尋 ::: :::warning 同剛剛的問題，不過這裡一定要標記! 作法如下 ```cpp= bool vis[1005][1005]; vis[3][1] = 1; //表示$(3,1)走訪過$ ``` ::: ## BFS題目 - [ ] [CSES Message Route](https://cses.fi/problemset/task/1667) - [ ] [CSES Counting Room](https://cses.fi/problemset/task/1192) - [ ] [Zero Judge d453](https://zerojudge.tw/ShowProblem?problemid=d453) - [ ] [TIOJ 2208](https://tioj.ck.tp.edu.tw/problems/2208) - [ ] [TIOJ 2180](https://tioj.ck.tp.edu.tw/problems/2180) **難度自上排下，TIOJ 2180需要 Priority Queue** # DFS ## 圖的走訪 :::info 給定一張圖，要怎麼樣歷遍所有點或找尋兩點路徑? $範例由1開始至4$ ![](https://i.imgur.com/c9Vux3i.png) ::: :::success 我們可以由 $1$ 號點開始，一直走，走到不能走為止 以圖為例，先從$1$號點開始 往二號，三號，五號，再到四號 到底後返回五號 再走至六號 時間複雜度： $O(E)$ $E$ 為圖的點數，一次歷遍 ::: :::warning 走訪小技巧 開一個 $vis$ 陣列，將走訪過的點標記 避免再次尋訪浪費時間 (視題目做標記) ```c++= vis[100005] = {}; vis[i] = 1; //代表一號點走過 ``` ::: ## DFS題目 - [ ] [Zero Judge c463](https://zerojudge.tw/ShowProblem?problemid=c463) - [ ] [Code Force 218C](https://codeforces.com/problemset/problem/218/C) - [ ] [TIOJ 1420](https://tioj.ck.tp.edu.tw/problems/1420)