内容预览

零、读前说明一、深度优先遍历1.1、深度优先的遍历过程1.2、深度优先的遍历实现代码二、广度优先遍历2.1、广度优先的遍历过程2.2、广度优先的遍历实现代码三、源码测试效果3.1、测试案例源码3.2、测试效果图四、简单的总结

零、读前说明

本文中所有设计的代码均通过测试，并且在功能性方面均实现应有的功能。设计的代码并非全部公开，部分无关紧要代码并没有贴出来。如果你也对此感兴趣、也想测试源码的话，可以私聊我，非常欢迎一起探讨学习。由于时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，也很欢迎大佬看见的话批评指正。 时隔三个月，我终于回来了，嘻嘻。。。。 。。。。。。。。收！摘要

图是一种非线性的数据结构，图的遍历指的是从图中的某一顶点出发，沿着一些边访问图中所有的顶点，使得每个顶点都被访问且仅被访问一次。根据遍历路径的不同，通常有两种遍历图的方法：深度优先遍历(Depth First Search )和广度优先遍历(Breadth First Search )。它们对无向图和有向图都适用，图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

书接前文，如果需要查看图的遍历的基础知识或者邻接矩阵的相关知识，请移步博文：

数据结构（廿五） – C语言版 – 图 - 图的遍历 – 邻接矩阵 - 深度/广度优先遍历/搜索（DFS、BFS）

所以本次接下来直接进入到基于邻接表的图的深度优先遍历和广度优先遍历。

一、深度优先遍历

1.1、深度优先的遍历过程

下面开始开始说明无向图的深度优先遍历的过程，其实有向图的深度遍历与无向图的深度优先遍历一致（唯一不同的就是两个顶点有连线但是不一定是邻接的关系，所以不再进行赘述）。

以下图为例，对于同一种图的结构进行无向图和有向图的分别表示描述（一无向图的为主，有向图的可以参考无向图的描述，基本上一致）。

 图1.1 图遍历的过程示意图 

同上图，我们可以根据图例画出对应图的邻接表表示形式，如下图所示。

图1.2 图的邻接表示意图

1、假设访问起始遍历的顶点为顶点A（图中 1 所指），同时标记为已访问（下同，不再描述）；

2、然后开始访问顶点A的邻接点，也就是开始访问顶点B、顶点C或者顶点D（我们在邻接表的增加边的时候链表采用的是头插入，所以后出现（顶点编号大的）的边在邻接链表的前部，在遍历的时候根据链表的顺序进行遍历），所以接下来应该遍历顶点D（图中 2 所指），然后遍历顶点D的邻接点E（图中 3 所指）；

3、然后开始遍历顶点E的邻接点顶点B（图中 4 所指）（在有向图中顶点 E 没有邻接点，所以将按照上述右边图所示标识进行后续的遍历，后续不在进行赘述）；

4、由图中可以看出来，顶点B有两个邻接点，分别为顶点A和顶点C，根据链接表中链表顺序，应该访问的顶点D（图中 5 所指），然后继续访问C的邻接点，为顶点A（图中淡色线条所指），经判断顶点A已经标记为已访问，所以开始回退（图中 6 所示）到顶点B；

5、继续遍历顶点B的邻接点顶点A（图中淡色线条所指），经判断顶点A已经标记为已访问不需要再遍历。继续遍历顶点B的邻接点顶点F（图中 7 所指）；

6、至此，所有顶点均遍历完成，然后依次返回到最初访问的顶点位置（图中 8、9、10、11 所指），遍历算法结束。

所以遍历的顺序为：A -> D -> E -> B -> C -> F

1.2、深度优先的遍历实现代码

实现代码中已经有了比较详细的注释，所以便不再进行说明，代码如下所示。

/*** 功 能：*深度优先遍历图的辅助函数 -- 递归实现* 参 数：*graph：要遍历的图*v ： 起始遍历的节点（在节点组中的编号/下标）*visited ：是否被访问的标识* 返回值：*无**/static void recursive_dfs(TLGraph *graph, int v, int visited[]){int i = 0;if (graph == NULL || v < 0 || visited == NULL)return;// 打印输出节点信息，也可以其它操作printf("%s ", (char *)graph->vertex[v]);// 设置访问的标志visited[v] = TRUE;// 循环获取所有的邻接节点for (i = 0; i < funLinkList.length(graph->first[v]); i++){// 获取到当前节点TListNode *node = (TListNode *)funLinkList.get(graph->first[v], i);// 判断是否访问过，没有则继续访问if (visited[node->adjvex] == FALSE){// 递归遍历访问recursive_dfs(graph, node->adjvex, visited);}}}/*** 功 能：*深度优先遍历图的函数* 参 数：*graph：要遍历的图*v ： 起始遍历的节点（在节点组中的编号/下标）* 返回值：*无**/int LGraph_DFS(LGraph *graph, int v){int *visited = NULL;TLGraph *tGraph = NULL;if (graph == NULL) goto ERROR;tGraph = (TLGraph *)graph;if ((v < 0) || (v > tGraph->count)) goto ERROR;// 为访问的标志申请空间并初始化visited = (int *)calloc(tGraph->count, sizeof(int));if (visited == NULL) goto ERROR;// 开始递归遍历recursive_dfs(tGraph, v, visited); // 对未访问的邻接顶点递归调用// 再次遍历所有节点，如果在上次访问中有没有被访问的节点（没有边连接），非连通图，那么以此节点开始继续访问for (int i = 0; i < tGraph->count; i++){if (visited[i] == FALSE)// 判断是否被访问recursive_dfs(tGraph, i, visited); // 对未访问的邻接顶点递归调用}printf("\n");free(visited);return 0;ERROR:return -1;}

二、广度优先遍历

2.1、广度优先的遍历过程

图中的形式有向图和无向图的顺序相差不大，所以就在一起描述。以下图为例。

图2.1 图的广度优先遍历示意图

1、假设访问起始遍历的顶点为顶点A，将顶点A入队列（图中 1 所指，入队列也是为了在访问完其中某个邻接点的后再访问其他邻接点），此时队列中为节点A；（图中 1 所指），同时标记为已访问（下同，不再赘述）；

2、然后将顶点A出队列，顶点A的遍历完成，然后开始访问顶点A的邻接点（分别为顶点 B 、顶点 C 、顶点 D 。（由于是按照邻接表进行遍历，并且链表采用的时候头插入方式，所以后插入的节点在链表的前面，所以遍历规则设定为按照链表的节点的顺序进行遍历，如果插入链表的位置不同，那么遍历的结果也不同））；

3、然后将顶点A的所有的没有被访问的邻接点入队列（入队列顺序从前到后依次为顶点 D、顶点 C、顶点 B，图中 2、4、6 所指），此时队列中为顶点 B、C、D；

4、然后将顶点D出队列（图中 2 所指），顶点D的遍历完成，然后将顶点D的所有的没有被访问的邻接点入队列（入队列的顺序为 E、A（由于 A 已经被访问，所以不再入队列），图中 8 所指），此时队列中的节顶点为 C、B、E ；

5、然后将顶点C出队列（图中 4 所指），顶点C的遍历完成，然后将顶点C的所有的没有被访问的邻接点入队列（其邻接点为顶点 B 和顶点 A （图中有向图没有顶点 A ），但是顶点 A、B 经判断已经被访问），则不再入队列，此时队列中的顶点为 B、E ；

6、然后将顶点D出队列（图中 6 所指），顶点B的遍历完成，此时顶点B的邻接点为顶点A、顶点C、顶点E、顶点F（图中有向图没有顶点 A、C ），且经判断顶点A、C、E已经被访问所以不再入队列，此时队列中的顶点为 E、F；

7、继续出队列为顶点E（图中 8 所指），有向图中顶点E没有邻接点，无向图中邻接点为 B 和 D ，经判断均已经被访问，所以也不再入队列；此时队列中顶点为 F ；

8、出队列顶点F（图中 10 所指），经判断顶点F的所有邻接点均已经被访问，没有可入队列的顶点，此时队列为空，遍历完成。

所以，遍历的顺序为：A -> D -> C -> B -> E -> F

2.2、广度优先的遍历实现代码

实现代码中已经有了比较详细的注释，所以便不再进行说明，代码如下所示。

/*** 功 能：*广度优先遍历图的辅助函数 -- 队列实现* 参 数：*graph：要遍历的图*v ： 起始遍历的节点（在节点组中的编号/下标）*visited ：是否被访问的标识* 返回值：*无**/static void bfs(TLGraph *graph, int v, int visited[]){if (graph == NULL || v < 0 || visited == NULL)return;// 创建一个队列LinkQueue *queue = fLinkQueue.create();if (queue == NULL) return;// v是下标，直接入队列当前节点（从graph->vertex偏移v个量的）的地址fLinkQueue.enqueue(queue, graph->vertex + v);// 设置当前节点的访问标志visited[v] = TRUE;// 循环读取链表中的所有节点while (fLinkQueue.length(queue) > 0){// 出队列当前节点，和前面接如队列相反操作，获取到下标的值（偏移量）v = (LVertex **)fLinkQueue.dequeue(queue) - graph->vertex;// 输出节点信息printf("%s ", (char *)graph->vertex[v]);// 遍历与它对应的邻接链表，遍历与此节点有关联的下一层的节点for (int i = 0; i < funLinkList.length(graph->first[v]); i++){// 获取邻接点表中的每一个节点TListNode *node = (TListNode *)funLinkList.get(graph->first[v], i);// 判断访问的标志if (visited[node->adjvex] == FALSE){// 入队列fLinkQueue.enqueue(queue, graph->vertex + node->adjvex);// 将找到的此顶点标记为已访问visited[node->adjvex] = TRUE;}}}// 销毁队列fLinkQueue.destroy(queue);}/*** 功 能：*广度优先遍历图的函数* 参 数：*graph：要遍历的图*v ： 起始遍历的节点（在节点组中的编号/下标）* 返回值：*无**/int LGraph_BFS(LGraph *graph, int v){TLGraph *tGraph = NULL;int *visited = NULL;if (graph == NULL) goto ERROR;tGraph = (TLGraph *)graph;if ((v < 0) || (v > tGraph->count)) goto ERROR;// 为访问的标志申请空间并初始化visited = (int *)calloc(tGraph->count, sizeof(int));if (visited == NULL) goto ERROR;bfs(tGraph, v, visited);// 再次遍历所有节点，如果在上次访问中有没有被访问的节点（没有边连接），非连通图，那么以此节点开始继续访问for (int i = 0; i < tGraph->count; i++){if (visited[i] == FALSE)// 判断顶点是否曾经访问过，没有访问过则继续访问bfs(tGraph, i, visited); // 递归遍历}printf("\n");free(visited);return 0;ERROR:return -1;}

三、源码测试效果

3.1、测试案例源码

根据上述深度优先遍历以及广度优先遍历的过程说明等，编写出相关的测试案例的实现代码，源码如下所示。

#include "../src/graph/graph.h"#include <stdio.h>#include <stdlib.h>#include <unistd.h>int main(int argc, char *argv[]){system("color "); // 颜色设置，用于在windows下终端显示的时候不明原因换行的问题printf("\n\e[1;31mLet's start with an example of undirected graph:\e[0m\n");LVertex const *v[] = {"A", "B", "C", "D", "E", "F"};LGraph *ungraph = funGraph.create((LVertex **)v, 6);// 添加边funGraph.edge.add(ungraph, 0, 1, 1, UNDIRECTED_GRAPH); // (A, B)funGraph.edge.add(ungraph, 0, 2, 1, UNDIRECTED_GRAPH); // (A, C)funGraph.edge.add(ungraph, 0, 3, 1, UNDIRECTED_GRAPH); // (A, D)funGraph.edge.add(ungraph, 1, 4, 1, UNDIRECTED_GRAPH); // (B, E)funGraph.edge.add(ungraph, 1, 5, 1, UNDIRECTED_GRAPH); // (B, F)funGraph.edge.add(ungraph, 2, 1, 1, UNDIRECTED_GRAPH); // (C, B)funGraph.edge.add(ungraph, 3, 4, 8, UNDIRECTED_GRAPH); // (D, E)// 显示funGraph.display(ungraph, FLAG_NOTDISPLAY_HINT);// 遍历 printf("DFS Start with vertex 'A': ");funGraph.traverse.dfs(ungraph, 0);printf("BFS Start with vertex 'A': ");funGraph.traverse.bfs(ungraph, 0);printf("DFS Start with vertex 'C': ");funGraph.traverse.dfs(ungraph, 2);printf("BFS Start with vertex 'C': ");funGraph.traverse.bfs(ungraph, 2);printf("BFS Start with vertex 'E': ");funGraph.traverse.dfs(ungraph, 4);printf("BFS Start with vertex 'D': ");funGraph.traverse.bfs(ungraph, 3);printf("\n\e[1;31mLet's start with an example of directed graph:\e[0m\n");LGraph *graph = funGraph.create((LVertex **)v, 6);// 添加边funGraph.edge.add(graph, 0, 1, 1, DIRECTED_GRAPH); // <A, B>funGraph.edge.add(graph, 0, 2, 1, DIRECTED_GRAPH); // <A, C>funGraph.edge.add(graph, 0, 3, 1, DIRECTED_GRAPH); // <A, D>funGraph.edge.add(graph, 1, 4, 1, DIRECTED_GRAPH); // <B, E>funGraph.edge.add(graph, 1, 5, 1, DIRECTED_GRAPH); // <B, F>funGraph.edge.add(graph, 2, 1, 1, DIRECTED_GRAPH); // <C, B>funGraph.edge.add(graph, 3, 4, 8, DIRECTED_GRAPH); // <D, E>// 显示funGraph.display(graph, FLAG_NOTDISPLAY_HINT);// 遍历 printf("DFS Start with vertex 'A': ");funGraph.traverse.dfs(ungraph, 0);printf("BFS Start with vertex 'A': ");funGraph.traverse.bfs(ungraph, 0);printf("DFS Start with vertex 'C': ");funGraph.traverse.dfs(ungraph, 2);printf("BFS Start with vertex 'C': ");funGraph.traverse.bfs(ungraph, 2);printf("BFS Start with vertex 'E': ");funGraph.traverse.dfs(ungraph, 4);printf("BFS Start with vertex 'D': ");funGraph.traverse.bfs(ungraph, 3);// 销毁funGraph.destroy(ungraph);funGraph.destroy(graph);printf("\n\e[1;32msystem exited with return code %d\e[0m\n\n", 0);return 0;}

3.2、测试效果图

根据上述测试代码，进行编译并测试效果以如下图所示。

图4.1 无向图遍历的过程示意图

四、简单的总结

遍历的实质：找到每个顶点的邻接点的过程。

深度优先遍历：一条道路走到黑的故事，是一个递归的定义，也是一个俄罗斯套娃的过程。

对于深度优先遍历，在遍历到有多个邻接点的位置的时候，不同的选择将会出现不同的遍历顺序。

邻接矩阵：如果设定了存储结构为邻接矩阵，那么基于邻接矩阵的遍历的顺序是固定的

邻接表：如果设定了存储结构为邻接表，那么不同的链表顺序也将导致有不同的遍历的顺序

对于稠密图：适合在邻接矩阵上进行深度优先遍历

对于稀疏图：适合在邻接表上进行深度优先遍历

广度优先遍历：wifi信号式的遍历。

对于广度优先遍历，甚至于所有的层序的遍历，都需要借助队列的辅助实现

后记

最近由于工作、项目各种事情、加上本身冬天手冷脚冷心更冷、身体也不好了，脑袋也不好了、心情就更加不好了，所以更新可以说狠狠狠缓慢，并且在写作过程中明显有点力不从心的感觉了，最近又有很多事情一个比一个要人命的感觉，本来数据结构后面的部分用的比较少，所以暂时就不再更新数据结构部分的内容。如果后续用到或者有比较宽松的时间的话会继续学习并且同时继续更新相关内容。

数据结构部分的内容基本上从开始更新到目前为止快要一年的时间了，到目前为止才基本上写完数据结构最基础的部分内容，非常感谢阅读并给我鼓励的读着大大们，你们的支持是我最大的动力。希望大佬们继续能够支持我！！！O(∩_∩)O哈哈~

好啦，废话不多说，总结写作不易，如果你喜欢这篇文章或者对你有用，请动动你发财的小手手帮忙点个赞，当然关注一波那就更好了，就到这儿了，么么哒(* ￣3)(ε￣ *)。

上一篇：数据结构（廿五） – C语言版 – 图 - 图的遍历 – 邻接矩阵 - 深度/广度优先遍历/搜索（DFS、BFS）

下一篇：数据结构（廿六） – C语言版 – 图 - 图的遍历 – 邻接表 - 深度/广度优先遍历/搜索（DFS、BFS）

数据结构（廿六） -- C语言版 -- 图 - 图的遍历 -- 邻接表 - 深度/广度优先遍历/搜索（DFS BFS）

如果觉得《数据结构（廿六） -- C语言版 -- 图 - 图的遍历 -- 邻接表 - 深度/广度优先》对你有帮助，请点赞、收藏，并留下你的观点哦！