图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可视为一种特殊的图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。
图的遍历比树的遍历要复杂得多，因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组 visited[] 来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。
广度优先搜索
广度优先搜索（Breadth-First- Search, BFS）类似于二叉树的层序遍历算法。基本思想是：首先访问起始顶点 ，接着由
出发，依次访问
的各个未访问过的邻接顶点
然后依次访问
的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。Dijkstra 单源最短路径算法和 Prim 最小生成树算法也应用了类似的思想。
换句话说，广度优先搜索遍历图的过程是以 为起始点，由近至远依次访问和
有路径相通且路径长度为 1，2，… 的顶点。广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。
广度优先遍历算法的伪代码如下：
bool visited[MaxVertexNum]; // 访问标记数组void BFSTraverse(Graph G) { // 对图G进行广度优先遍历for (int i = 0; i < G.vexnum; ++i) {visited[i] = false; // 访问标记数组初始化}InitQueue(Q); // 初始化辅助队列Qfor (int j = 0; j < G.vexnum; ++j) { // 从0号顶点开始遍历if (!visited[j]) { // 对每个连通分量调用一次 BFSBFS(G, j);}}}//广度优先遍历void BFS(Graph G, int v) { //从顶点v出发，广度优先遍历图Gvisit(v); //访问初始顶点vvisited[v] = true; //对v做已访问标记Enqueue(Q, v); //顶点v入队列Qwhile (!isEmpty(Q)) {DeQueue(Q, v); //顶点v出队列for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {//检测v所有邻接点if (!visited[w]) { // w为v的尚未访问的邻接顶点visit(w); //访问顶点wvisited[w] = true; //对w做已访问标记EnQueue(Q, w); //顶点w入队列}// if}// for}// while}
- 同一个图的邻接矩阵表示方式唯一，因此广度优先历序列唯一
- 同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一
辅助数组 visited[] 标志顶点是否被访问过，其初始状态为 false 。在图的遍历过程中，一旦某个顶点 被访问，就立即置
visited[i] 为 true ，防止它被多次访问。
图的广度优先搜索的过程与二叉树的层序遍历是完全一致的， 这也说明了图的广度优先搜索遍历算法是二叉树的层次遍历算法的扩展。图的广度优先遍历还可用于求一些问题的最优解,
BFS 算法的性能分析
无论是邻接表还是邻接矩阵的存储方式，BFS 算法都需要借助一个辅助队列 Q， 个顶点均需入队一次，在最坏的情况下，空间复杂度为
#card=math&code=O%28%7CV%7C%29&id=EVoMz) 。
采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次）， 故时间复杂度为 #card=math&code=O%28%7CV%7C%29&id=ajz1u) ，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为
#card=math&code=O%28%7CE%7C%29&id=e9ePO) ， 算法总的时间复杂度为
#card=math&code=O%28%7CV%7C%2B%7CE%7C%29&id=Ha234)。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为
#card=math&code=O%28%7CV%7C%29&id=lY8dT) ，故算法总的时间复杂度为
#card=math&code=O%28%7CV%7C%5E2%29&id=osZ5r) 。
广度优先生成树
在广度遍历的过程中，我们可以得到一棵遍历树，称为广度优先生成树。需要注意的是，一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一， 故其广度优先生成树也是不唯一的。
深度优先搜索
与广度优先搜索不同，深度优先搜索（Depth-First-Search，DFS）类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。
它的基本思想如下：首先访问图中某一起始顶点 ，然后由
出发，访问与
邻接且未被访问的任一顶点
，再访问与
邻接且未被访问的任一顶点
…… 重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。
一般情况下，其递归形式的算法十分简洁，算法过程如下：
bool visited[MaxVertexNum]; // 访问标记数组
void DFSTraverse(Graph G) { // 对图 G 进行深度优先遍历
for (int v = 0; v < G.vexnum; ++v) {
visited[v] = false; // 初始化已访问标记数据
}
for (int v = 0; v < G.vexnum; ++v) {
if (!visited[v]) {
DFS(G, v);
}
}
}
void DFS(Graph G, int v) {
visit(v); // 访问顶点 v
visited[v] = true; // 设已访问标记
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighor(G, v, w)) {
if (!visited[w]) { // w 为 u 的尚未访问的邻接顶点
DFS(G, w);
}
}
}
注意：图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同，生成的邻接表也不同。因此，对于同样一个图，基于邻接矩阵的遍历所得到的 DFS 序列和 BFS 序列是唯一的，基于邻接表的遍历所得到的 DFS 序列和 BFS 序列是不唯一的。
DFS 算法的性能分析
DFS 算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为 #card=math&code=O%28%7CV%7C%29&id=jnvNA)。
遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为 #card=math&code=O%28%7CV%7C%29&id=voCDC) ，故总的时间复杂度为
#card=math&code=O%28%7CV%7C%5E2%29&id=TxLn7)。以邻接表表示时，查找所有顶点的邻接点所需的时间为
#card=math&code=O%28E%29&id=nyiCS)，访问顶点所需的时间为
#card=math&code=O%28%7CV%7C%29&id=zl8p1)，此时，总的时间复杂度为
#card=math&code=O%28%7CV%7C%2B%7CE%7C%29&id=DPz37) 。
深度优先的生成树和生成森林
与广度优先搜索一样，深度优先搜索也会产生一棵深度优先生成树。当然，这是有条件的，即对连通图调用 DFS 才能产生深度优先生成树，否则产生的将是深度优先生成森林。与 BFS 类似，基于邻接表存储的深度优先生成树是不唯一的。
图的遍历与图的连通性
图的遍历算法可以用来判断图的连通性。
对于无向图来说，若无向图是连通的，则从任一结点出发，仅需一次遍历就能够访问图中的所有顶点；若无向图是非连通的，则从某一个 顶点出发，一次遍历只能访问到该顶点所在连通分量的所有顶点，而对于图中其他连通分量的顶点，则无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，则能够访问到图中的所有顶点，否则不能访问到所有顶点。
故在 BFSTraverse() 或 DFSTraverse() 中添加了第二个 for 循环，再选取初始点，继续进行遍历，以防止一次无法遍历图的所有顶点。对于无向图，上述两个函数调用 BFS(G,i) 或 DFS(G,i) 的次数等于该图的连通分量数；而对于有向图则不是这样，因为一个连通的有向图分为强连通的和非强连通的，它的连通子图也分为强连通分量和非强连通量，非强连通分量一次调用 BFS(G,i) 或 DFS(G, i) 无法访问到该连通分量的所有顶点。
若有收获，就点个赞吧
0 人点赞
