前面的文章中我们学习了图的基本概念和存储结构，大家可以通过下面的链接学习：
这篇文章就来学习一下图的重要章节——图的遍历。
目录
一，图的遍历定义：
二，深度优先搜索(DFS)
连通图的深度优先遍历
邻接矩阵法实现DFS
邻接表法实现DFS
DFS算法效率分析：
非连通图的深度优先遍历
三， 广度优先搜索（BFS）
邻接矩阵法实现BFS
邻接表法实现BFS
BFS算法效率分析：
DFS与BFS算法效率比较
从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。
图遍历的实质：找每个顶点的邻接点的过程。
要进行图的遍历，我们需要知道图的特点，从而用合适，高效的方法来实现遍历。
图有哪些特点？
图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。
那么，如何避免在遍历时重复访问？
解决思路：
设置辅助数组 visited [n ]，用来标记每个被访问过的顶点。
初始状态为0
被访问，改 visited [i]为1，防止被多次访问。
图常用的遍历有两种：
深度优先搜索（Depth First Search,DFS）
广度优先搜索(Breadth First Search,BFS)
引例：
点亮迷宫中所有的灯，我们会一条道走到头，如果走不动了，再往回退寻找其他没有走过的。
因此我们可以总结DFS的详细归纳：
如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
仿树的先序遍历过程
先根，再左子树，最后右子树。
下面是一个练习：
它的深度优先搜索结果是：2→1→3→5→4→6
那么，在计算机中我们该如何实现DFS的过程？
在上一篇文章中我们学习了图的存储结构的邻接矩阵法，借助一个辅助数组 visited [n ]来保存邻接矩阵的信息。
在编程时，使用邻接矩阵法DFS的实现可以采用递归算法：
而下面是完整的c语言使用邻接矩阵法来实现图的深度优先搜索：
注意：
这里我使用了C语言的一个库#include <stdbool.h>，来声明我使用了布尔型数据
大家也可以自己定义布尔类型，true代表1为真，false代表0为假
typedef int bool;
#define true 1
#define false 0
输入实例：
输出结果：
我们知道图的存储结构除了邻接矩阵法之外还有邻接表法，那么使用邻接表法能否实现图的深度优先搜索？
当然可以，同样要借助辅助数组visited [n ]
使用邻接表法DFS的实现也可以采用递归算法：
在实际的编程中，使用邻接表法实现的DFS代码：
输出结果：
Depth First Traversal: 0 2 1 4 3
用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。
用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。
结论：
稠密图适于在邻接矩阵上进行深度遍历；
稀疏图适于在邻接表上进行深度遍历。
如下图例子，连通分量分开访问，先DFS访问完第一个，再访问第二个。
同样是点亮迷宫中的灯案例，广度优先搜索没有一条道走到黑，而是每个道都走，一层一层实现遍历。
简单归纳：
在访问了起始点v之后，依次访问 v的邻接点；
然后再依次访问这些顶点中未被访问过的邻接点；
直到所有顶点都被访问过为止。
BFS基本思想：——仿树的层次遍历过程
在计算机中，如何实现BFS？
与DFS相比，除辅助数组visited [n ]外，还需再开一辅助队列。
算法思想：
从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。
只要队列不空，则重复下述处理。
① 队头顶点u出队。
② 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队。
同样对于BFS可以使用邻接矩阵或邻接表法来实现。
输入案例
输出结果
输出结果：
如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。
用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。
空间复杂度相同，都是O(n)(借用了堆栈或队列）；
时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。
最后是一个小练习
图的遍历到此就结束啦，如果文章对你有用的话请点个赞支持一下吧！
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/2492.html