图的广度优先遍历

我一直觉得图的遍历没有地图类型的题目难，遍历嘛，每个点都走一遍就行了。

但是给定地图求面积啊，数量啊的那种题目，花样挺多的。

图的遍历真挺难把人绕晕的，关于广度优先，理解好层层递进这个概念就好。

• 还是这张图，上次我用了深度优先方法去遍历它：图的深度优先遍历
• 这次用广度优先（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;
}

遍历结果为