广度优先遍历

首先来说一下广度优先遍历，看名称很高大上的样子，其实它的原理跟树的层次遍历几乎一模一样。那么我就以树的层次遍历简单说明一下原理。

要实现层次遍历需要创建队列作为辅助。

层次遍历收先将根结点入队，如下图：

然后把A出队，把它的左右儿子入队：

把B出队，将B的左右儿子入队，也就是谁出队就把谁的左右儿子入队：

C出队，把C的左右儿子入队，依次循环下去…..，直到全部都输出，简单的来看一下，大家是否发现树的输出顺序是ABCDEF,也就是说一层一层的输出。这也是广度优先遍历的原理。

下面就直接将代码：

大家先不要慌，先把我图中绿色方框去掉，那么代码变成在执行什么内容。大家先想想，其实你会的，并不难，想明白了就好理解了。

不知道大家能不能看出来，除去绿色方框的代码，剩下的代码其实就是在创建邻接表。

那么我们就重点来分析绿色方框的代码就行了，没必要全部都要讲，浪费大家阅读其他文章的时间。

①、先上主函数，主函数就是在创建一个广度优先遍历的函数BFS，需要注意的是蓝色方框的内容，蓝色方框代码就是在定义从哪个顶点开始遍历，如果你的顶点名称是ABCDEF这几个字母，你可以选择ABCDEF其中一个字母作为整个遍历的开始，Findsub函数的作用顶点名称（ABCDEF）所在顶点表中的下标。Findsub函数代码内容也在下面了，很简单的一段代码

②、在对BFS函数讲解之前献给大家看一下队列结构：

其中int* data和int* visited两者不是简单的指针，注意他是在结构体内的，他们是柔性数组结构，为什么要这样设计，有什么用。首先我就讲一点它的好处，具体在这里起到什么作用下面会讲到，柔性数组最大的特点是它是一个可以调整大小的数组，一般的数组大小都是固定的，当你想要在添加数据的时候就溢出了，这时你得重新去定义它的大小，是不是很麻烦呢。

其他两个成员变量是用来遍历队列用的，先不管，继续往下。

③、这时就到了BFS函数了。

还算是有点长的。但要成为大佬的你们不算什么。

红色方框的代码作用是为队列开辟空间，聪明的你也许会发现我的代码开辟了三个空间，后面两个空间是给谁的呢，上面我们不是说到了柔性数组是可以调整大小的吗，就是给队列和辅助数组开辟的空间，这是你应该知道怎么使用柔性数组了吧，也知道它的强大了吧，它的大小会随着G->vernums大小的改变而改变，也就是根据你输入的顶点数的大小改变而改变，不需要担心数组溢出的问题。

蓝色方框是将顶点入队，入队的顶点所在顶点数组下标要赋给辅助数组visited，也就是被访问过的顶点标记为1，没访问过的标记为0。

粉色方框代码是重点，需要点耗费点脑力，我还是用图来说明一下吧。因为表达有限，说明在下一张图，对应这粉色方框来看哦。辅助数组的作用也在最后了哦。