圖的廣度優先遍歷

我一直覺得圖的遍歷沒有地圖類型的題目難，遍歷嘛，每個點都走一遍就行了。

但是給定地圖求面積啊，數量啊的那種題目，花樣挺多的。

圖的遍歷真挺難把人繞暈的，關于廣度優先，理解好層層遞進這個概念就好。

• 還是這張圖，上次我用了深度優先方法去遍歷它：圖的深度優先遍歷
• 這次用廣度優先（BFS）法去遍歷它

---

代碼實現

#include<stdio.h>int book[2000], a[2000][2000], que[2000];
int sum, n, m;
int head, tail;int main()
{int i, j, m, x, y;int cur;scanf("%d %d", &n, &m);for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)if (i == j)a[i][j] = 0;elsea[i][j] = 99999999;for (i = 1; i <= m; i++){scanf("%d %d", &x, &y);a[x][y] = 1;a[y][x] = 1;}head = 1;tail = 1;que[tail] = 1;book[1] = 1;tail++;while (head < tail){//當前正在訪問的頂點的編號cur = que[head];// 從1~n進行嘗試for (i = 1; i <= n; i++){if (a[cur][i] == 1 && book[i] == 0){que[tail] = i;tail++;book[i] = 1;}//如果tail>n則表示所有頂點都被訪問過if (tail > n){break;}}//這里不要忘記，拓展完之后，要將頭指針+1head++;}for (i = 1; i < tail; i++){printf("%d ", que[i]);}return 0;
}

遍歷結果為

總結

以上是生活随笔為你收集整理的[C] 图的广度优先遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。