前面介紹了深度優先搜索，可知DFS是以深度作為第一關鍵詞的，即當碰到岔道口時總是先選擇其中的一條岔路前進，而不管其他岔路，直到碰到死胡同時才回傳岔道口并選擇其他岔路，
接下來將介紹的廣度優先搜索（Breadth FirstSearch，BFS)則是以廣度為第一關鍵詞，當碰到岔道口時，總是先依次訪問從該岔道口能直接到達的所有結點，然后再按這些結點被訪問的順序去依次訪問它們能直接到達的所有結點，以此類推，直到所有結點都被訪問為止，
這就跟平靜的水面中投入一顆小石子一樣，水花總是以石子落水處為中心，并以同心圓的方式向外擴散至整個水面，從這點來看
和DFS那種沿著一條線前進的思路是完全不同的，
廣度優先搜索（Breadth First Search, BFS）遍歷類似于樹的按層次遍歷的程序，則是以廣度為第一關鍵詞，當碰到岔道口時，總是先依次訪問從該岔道口能直接到達的所有結點，
然后再按這些結點被訪問的順序去依次訪問它們能直接到達的所有結點，以此類推，直到所有結點都被訪問為止，
廣度優先搜索的整個演算法程序很像一個佇列，因此，廣度優先搜索（Breadth First Search, BFS）一般由佇列實作，且總是按層次進行遍歷，
其基本寫法如下（可用作模板用）：
void BFS(int s) { queue<int> q; q.push(s); while (!q.empty()) { 取出隊首元素top 將隊首元素出隊 訪問隊首元素top 將top的下一層結點中未曾入隊的結點全部入隊，并設定為已入隊 ， } }
下面是對該模板中每一個步驟的說明，請結合代碼一起看：
①定義佇列q，并將起點s入隊，
②寫一個 while回圈，回圈條件是佇列q非空，
③在 while回圈中，先取出隊首元素top，然后訪問它（訪問可以是任何事情，例如將其輸出），訪問完后將其出隊，
④將top的下一層結點中所有未曾入隊的結點入隊，并標記它們的層號為now的層號加1，同時設定這些入隊的結點已入過隊
⑤回傳②繼續回圈，
下面舉一個例子，希望讀者能從中學習BFS的思想是如何通過佇列來實作的：
題目：
給出一個m* n的矩陣，矩陣中的元素為0或1，稱位置(x, y)與其上下左右四個位置(x, y + 1)、(x, y - 1)、(x + 1, y)、(x - 1, y)是相鄰的，
如果矩陣中有若干個1是相鄰的（不必兩兩相鄰），那么稱這些1構成了一個“塊”，求給定的矩陣中“塊”的個數，
0111001
0010000
0000100
0001110
1110100
1111000
例如上面的6*7的矩陣，塊的個數為4；
對這個問題，求解的基本思想是：
列舉每一個位置的元素，如果為0，則跳過；如果為1，則使用BFS查詢與該位置相鄰的4個位置（前提是不出界），判斷它們是否為1
（如果某個相鄰的位置為1，則同樣去査詢與該位置相鄰的4個位置，直到整個“1”塊訪問完畢），
而為了防止走回頭路，一般可以設定一個bool型陣列inq（即 In queue的簡寫）來記錄每個位置是否在BFS中已入過隊，
現在有一個小技巧是：對當前位置(x, y)來說，由于與其相鄰的四個位置分別為(x, y + 1)、(x, y - 1)、(x + 1, y)、(x - 1, y)，
那么不妨設定下面兩個增量陣列，來表示四個方向（豎著看即為(0, 1)、(0, -1)、(1, 0)、(-1, 0)），
int X[] = { 0,0,1,-1 }; int Y[] = { 1,-1,0,0 };
這樣就可以使用for回圈來列舉4個方向，以確定與當前坐標(nowX, nowY)相鄰的4個位置，如下所示：
for (int i = 0; i < 4; i++) { newX = nowX + X[i]; newY = nowY + Y[i]; }
下列給出使用BFS搜索方法寫出的代碼：
#include<cstdio> #include<queue> using namespace std; const int maxn = 100; struct node { int x, y; }Node; int m, n; int matrix[maxn][maxn]; bool inq[maxn][maxn] = {false}; int X[4] = { 0,0,1,-1 }; int Y[4] = { 1,-1,0,0 }; bool judge(int x, int y) { if (x >= n || x < 0 || y >= m || y < 0) return false;//是否越界，越界回傳個false if (matrix[x][y] == 0 || inq[x][y] == true) return false;//當前位置是否為0，是否已經入過隊，回傳false return true;//當前位置為1，且沒有入過隊 } void BFS(int x, int y) { queue<node> Q; Node.x = x; Node.y = y; Q.push(Node); inq[x][y] = true; while(!Q.empty()){ node top = Q.front(); Q.pop(); for (int i = 0; i < 4; i++) { int newX = top.x + X[i]; int newY = top.y + Y[i]; if (judge(newX, newY)) { Node.x = newX; Node.y = newY; Q.push(Node); inq[newX][newY] = true; } } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &matrix[i][j]); } } int ans = 0; for (int x = 0; x < n; x++) { for (int y = 0; y < m; y++) { if (matrix[x][y] == 1 && inq[x][y] == false) { ans++; BFS(x, y); } } } printf("%d", ans); return 0; }
如果使用DFS搜索的話：
#include<cstdio> #include<queue> using namespace std; const int maxn = 100; struct node { int x, y; }Node; int m, n; int matrix[maxn][maxn]; bool inq[maxn][maxn] = { false }; int X[4] = { 0,0,1,-1 }; int Y[4] = { 1,-1,0,0 }; bool judge(int x, int y) { if (x >= n || x < 0 || y >= m || y < 0) return false; if (matrix[x][y] == 0 || inq[x][y] == true) return false; return true; } void DFS(int x, int y) { //當前點是塊中點，先標記，然后橫向遍歷解答樹所有子節點進行DFS inq[x][y] = true; for (int i = 0; i < 4; i++) {int newX = x + X[i]; int newY = y + Y[i]; if (judge(newX, newY)) DFS(newX, newY); } } } int main() { scanf("%d%d", &n, &m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { scanf("%d", &matrix[i][j]); } } int ans = 0; for (int x = 0; x < n; x++) { for (int y = 0; y < m; y++) { if (matrix[x][y] == 1 && inq[x][y] == false) { ans++; DFS(x, y); } } } printf("%d", ans); return 0; }
相似的練習：
迷宮問題
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/279786.html
標籤：其他
下一篇：迷宮問題（BFS）+（DFS）