C语言数据结构与算法之图的遍历(二)

成精的你

前言 

在上一章的内容中我们使用了深度优先搜索来进行遍历，这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下:

广度优先搜索过程

使用广度优先搜索来遍历这个图的过程如下。
首先以一个未被访问过的顶点作为起始顶点，比如以1号点作为起始顶点。
将1号点放到队列中，然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中，如下图：

接下来将2号顶点相邻的未访问过的顶点4号放入到队列中。到此所有的顶点都访问过了，遍历结束。如下图：

主要思想 

首先以一个未被访问过的顶点作为起始顶点，访问其所有相邻的点
然后对每个相邻的的点，再访问他们相邻的未被访问过的顶点，直到所有的顶点都被访问过，遍历结束。

代码实现  

1. #include <stdio.h>
   
2. int main()
   
3. {
   
4.     int i, j, m, a, b, cur,n, book[101] = { 0 }, e[101][101];
   
5.     int que[10001], head, tail;
   
6.     scanf("%d %d", &n, &m);
   
7.     //初始化二维矩阵
   
8.     for (i = 1; i <= n; i++)
   
9.         for (j = 1; j <= n; j++)
   
10.             if (i == j) e[i][j] = 0;
    
11.             else e[i][j] = 99999999;        //我们假设99999999为x
    
12. 
    
13.     //读入顶点之间的边
    
14.     for (i = 1; i <= n; i++)
    
15.     {
    
16.         scanf("%d %d", &a, &b);
    
17.         e[a][b] = 1;
    
18.         e[b][a] = 1;        //因为该图为无向图
    
19.     }
    
20. 
    
21.     //队列初始化
    
22.     head = 1;
    
23.     tail = 1;
    
24. 
    
25.     //从1号顶点出发，将1号顶点加入队列
    
26.     que[tail] = 1;
    
27.     tail++;
    
28.     book[1] = 1;//标记1号顶点已经入列
    
29. 
    
30.     //当队列不为空时循环
    
31.     while (head < tail && tail <= n)
    
32.     {
    
33.         cur = que[head];  //当前正在访问的顶点编号
    
34.         for (i = 1; i <= n; i++)
    
35.         {
    
36.             //判断从顶点cur到顶点i是否有边，并判断顶点i是否访问过
    
37.             if (e[cur][i] == 1 && book[i] == 0)
    
38.             {
    
39.                 //如果从顶点cur到顶点i右边，且顶点i没有被访问过，将顶点i入列
    
40.                 que[tail] = i;
    
41.                 tail++;
    
42.                 book[i] = 1; //标记表示已经访问过
    
43. 
    
44.             }
    
45.             if (tail > n)  //表示所有点都已经访问过
    
46.                 break;
    
47.         }
    
48. 
    
49.         head++;
    
50.         //注意这个地方，不要忘记head++后，才能继续向下拓展
    
51.     }
    
52. 
    
53.     for (i = 1; i < tail; i++)
    
54.         printf("%d",que[i]);
    
55. 
    
56. 
    
57. }

复制代码

到此这篇关于C语言数据结构与算法之图的遍历(二)的文章就介绍到这了,更多相关C语言 数据结构 图的遍历内容请搜索晓枫资讯以前的文章或继续浏览下面的相关文章希望大家以后多多支持晓枫资讯！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

蒙蒙D路飞

路过，支持一下

梦若潇寒酶

感谢楼主，顶。

妩媚小莫

感谢楼主分享。

刘p是我亲弟

顶顶更健康！！！