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

谁践踏了优雅 2022-12-03 13:24 119阅读 0赞

### 内容预览 ###

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

# 零、读前说明 #

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

摘要

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

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

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

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

# 一、深度优先遍历 #

## 1.1、深度优先的遍历过程 ##

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70][]   图1.1 图遍历的过程示意图

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 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、广度优先的遍历过程 ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 2][]图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、测试效果图 ##

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 3][]图4.1 无向图遍历的过程示意图

# 四、简单的总结 #

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

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

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

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

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

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

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

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

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

后记

最近由于工作、项目各种事情、加上本身冬天手冷脚冷心更冷、身体也不好了，脑袋也不好了、心情就更加不好了，所以更新可以说狠狠狠缓慢，并且在写作过程中明显有点力不从心的感觉了，最近又有很多事情一个比一个要人命的感觉，本来数据结构后面的部分用的比较少，所以暂时就不再更新 **数据结构** 部分的内容。如果后续用到或者有比较宽松的时间的话会继续学习并且同时继续更新相关内容。  
  数据结构部分的内容基本上从开始更新到目前为止快要一年的时间了，到目前为止才基本上写完数据结构最基础的部分内容，非常感谢阅读并给我鼓励的读着大大们，你们的支持是我最大的动力。希望大佬们继续能够支持我！！！O(∩\_∩)O哈哈~  
    
  好啦，废话不多说，总结写作不易，如果你喜欢这篇文章或者对你有用，请动动你发财的小手手帮忙**点个赞**，当然**关注一波**那就更好了，就到这儿了，么么哒(\* ￣3)(ε￣ \*)。

![20201117155233402.gif][]

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

[_ C_ _ _ - _ _ _ - _DFS_BFS]: https://blog.csdn.net/zhemingbuhao/article/details/108393792
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70]: /images/20221123/d7742c20f741468f96c7be397540c6f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 1]: /images/20221123/e4b2d3bc43d8491b8b78fe58819eefd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 2]: /images/20221123/e97e5427c09d4b5eb91cf4bea2dff1e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poZW1pbmdidWhhbw_size_16_color_FFFFFF_t_70 3]: /images/20221123/f20e9a52fa8f40858bee48d6ab1637f3.png
[20201117155233402.gif]: /images/20221123/dc8d40a5f8354f24ae801694d5ed701f.png
[_ C_ _ _ - _ _ _ - _DFS_BFS 1]: https://blog.csdn.net/zhemingbuhao/article/details/108395355