图的遍历

图的遍历指的是从某一顶点出发，按照某种搜索方法访问图中的所有顶点，有且仅访问一次。

广度优先搜索(BFS, Breadth-First-Search)

类似于二叉树的按层遍历的算法。基本思想：以$v$为起始点，由近至远依次访问和$v$有路径相通且路径长度为$1,2,…$的顶点。使用队列实现广度优先搜索算法。

辅助数组

• $color[|V|]$表示顶点状态：白色顶点表示顶点尚未被发现；灰色顶点表示表示已加入队列，无需再次入队；黑色顶点表示顶点已访问。
• $pred[|V|]$表示发现顶点的顶点，即树中子结点的父结点。
• $dist[|V|]$表示该顶点离起始点的距离。

  代码

  1 2	for(int = 0;i < )

BFS算法的空间复杂度最坏情况是$O(|V|)$，因为辅助队列最坏情况保存所有顶点。采用邻接表存储时，算法时间复杂度是$O(|V|+|E|)$。

广度优先搜索方向的应用有求解最短路径问题。

广度优先树

在广度遍历的过程中，得到的树，称为广度优先生成树。

深度优先搜索(Depth-First-Search, DFS)

类似于二叉树的先序遍历，尽量深地搜索一个图。基本思想：以$v$为起始点，访问与$v$邻接且未被访问的任意一个顶点$w_1$，再访问与$w_1$邻接且未被访问的任意一个顶点$w_2$…重复以上过程。当不能继续向下访问的时候，依次退到最近被访问的顶点，若它还有未被访问的邻接顶点，则从该点继续上述搜索过程，直到整张图均被访问过为止。

辅助数组

• $color[|V|]$表示顶点状态：白色顶点表示顶点尚未被发现；灰色顶点表示已找到，正在处理（在递归栈中）；黑色顶点表示顶点已处理完，退出递归栈返回，
  在DFS函数$return$前将顶点变为黑色。
• $pred[|V|]$表示发现顶点的顶点，即该顶点的上一个相邻的顶点。可以称为父数组。

  代码

  $DFS(G)$

  输入：图$G$

输出：父数组$pred$，发现时间数组$discover$，结束时间数组$finish$

1
2
3
4
5
6
7
8

for v ∈ V do:
    pred[v] = NULL
    color[v] = White
time = 0
for v ∈ V:
    if color[v] == White then
        DFS_visit(G,v)
return pred, discover, finish

访问顶点$v$的函数 $DFS_visit(G,v)$

1
2
3
4
5
6
7
8
9
10
11

color[v] = Gray
time = time + 1
discover[v] = time //记录发现顶点v的时间
for u ∈ G.Adj[v] do
    if color[u] == White then
        pred[u] = v
        DFS_visit(G,u)
time = time + 1
color[v] = Black
finish[v] = time
return

DFS算法复杂度分析

需要访问$|V|$个顶点，访问每个顶点的时间复杂度是$T_v=O(1+deg(v))$，其中$1$指的是访问顶点操作的时间复杂度，$deg(v)$指的是访问相邻结点的时间复杂度。

无向图深度优先搜索中边的种类

经过深度优先搜索后，并不是图中的所有边都会访问到，无向图中边只有两类：树边和非树边。

• 树边：在深度优先搜索中访问到的边。
• 后向边：非树边。但是边的两端顶点在深度优先树中是祖先和后代的关系。
  • 在无向图中，非树边都是后向边。

    有向图深度优先搜索中边的种类

    有向图中的边分为四类：
• 树边：在深度优先搜索中访问到的边，即在深度优先树的边。
• 前向边：从前代向后代的边。不在深度优先树中的边，方向是祖先指向后代。
• 后向边：从后代向前代的边。不在深度优先树中的边，方向是后代指向祖先。
• 横向边：不在深度优先树中的边，但是两个顶点属于平级关系。

  点的性质

  如果$[discover[v], finish[v]]$包含$[discover[u], finish[u]]$，说明顶点$u$是$v$的后代。

图的遍历算法的应用

图的遍历算法可以用来判断图的连通性。如果图是连通的，则一次访问即可访问图中的所有顶点。

• ← Previous Post
• Next Post →