第七章 图的遍历

• 解决图的问题，大多数时候需要能够不重复的完全遍历每个节点，是求解问题的基础。
• 和树的遍历类似，图的遍历希望从图的某个顶点出发遍历剩余所有顶点；但因为图可能形成环，在访问某顶点后可能有绕回该点。
• 下面介绍两种最基本图的遍历算法：深度优先搜索（）、广度优先搜索（）。他们均适用于有向图、和无向图。

深度优先搜索DFS

• 所谓深度，可以理解为一个人从起点找一条路出发一直前进，不碰壁不回头；回头后，再找一条新路径继续前进，直到所有位置都被访问过。

• 例如，如下无向图

  z3Cqt1.png

  假设起点为，顺序为：

  取决于从哪条路径先开始。

• 深度优先搜索树：利用深度优先搜索得到的访问序列构成的树；

  z3Pu7j.png

  假设从顶点出发，得到的一种深度优先搜索树如下，顶点的表示的先序号、后序号，即第几个被访问的。

  • 注意当不能继续前进时，采用回退的方式，看是否可以继续；回退到时，发现未被遍历的，进而得到如下深度优先树；

• ，表示前序（第几个被访问），表示后序（折返时第几个被重新访问）；

  • 树边：DFS中，如果在探索时，是首次被访问，则边为树边；
  • 回边：其他所有的边（）;
  • 后，连接的已经被访问，此时得以自增；
  • 折返到时，仍然可以继续深度搜索，直到访问到，回退；
  z3PGcT.png

  对于有向图，前序、后序的概念相同，新增几个边的概念；

  • 树边：在探索边时，是首次被访问的，则是树边；
  • 回边：在迄今构建的深度优先搜索树，是的祖先，且当探索时顶点已经被访问过，这样的边是回边；
  • 前向边：在迄今构建的深度优先搜索树，是的子孙，且当探索时顶点已经被访问过，这样的边是回边；
  • 横跨边：其他所有的边。
  • 为验证自己画的边是否缺失或多余，可以将自己的树与图中的边对比，应当是能够一一对应的。
  z8T5ef.md.png
  z87Fp9.png
  这里只列出了这种访问顺序。

DFS

输入：有向图或无向图G=(V, E)。

输出：在相应的深度优先搜索树中顶点的前序和后序。

• 递归法

predfn <- 0; postdfn <- 0
for each v in V
    visited[v] <- false
end for
for each v in V
    if visited[v] = false then dfs(v)
end for

过程：dfs(v)
visited[v] <- true
predfn <- predfn + 1 #dfs开始时访问到某个结点，即可得到其前序
for each (v, w) in E
    if visited[w] = false then dfs(w)
end for
postdfn <- postdfn + 1 #折返时对postdfn进行赋值

• 堆栈法（未进行前序后序记录）

  1. 初始时，入栈起点；

  2. 每次出栈一个顶点并输出，将与其直接相连的顶点入栈；

  3. 重复执行第二步直到栈为空；

  z3Fky8.png

for each v in V
    visited[v] <- false
push(v, S) #S为堆栈
while S not empty
    v <- pop(S)
    visited[v] <- true
    output: v
    for each (v,w) in E
        if visited[w] = false then
            push(w, S)
        end if
    end for
end while

深度优先搜索的应用

图的无回路性

• 回忆：什么是连通？图中的任一个顶点到其他顶点至少存在一条路径。

• 设是一个有个顶点，条边的有向或无向图。为了测试是否存在回路，我们可以进行一次，若出现回边（即访问过的顶点仍然要被判断）,则存在回路否则不存在。

• 若是一个连通无向图，那么当且仅当时，图变成一个树时，不存在回路。

拓扑排序

• 定义：给定一个有向无回路图，找到一个这样的线性序列：对于相邻的，如果排在的前面，说明到有一条边或者与无联系。

• 例如下图,

  z8HG8J.png
  • 每次选择入度为的顶点，均可作为第一个选择的，以为例：那么将和它的边从图中删除，此时仅的入度为，再次选择；此时的入度都为，选择；此时仅的入度为，选择······最后得到的序列为；

• 为实现拓扑排序，可以对每个顶点增加入度、出度两个数据项并初始化。

  1. 初始化时，将入度为的顶点入队；

  2. 从队列中取出一个顶点并输出，并更新与之相关顶点的入度，再次选择入度为的顶点入队；

  3. 重复第二步直到队列为空；

  • 此算法只能输出一种拓扑排序（对于确定的图可能存在多种拓扑排序）；

• 另一种利用深度优先算法，计数器定义了图的反拓扑系列，我们只需要在里自增时增加一个输出步骤，把输出结果反过来就是拓扑排序。

寻找图的关节点

• 在多于两个顶点的无向图中，存在一个顶点，如果有不同于的两个顶点，在间的任何路径都必定经过则称是关节点。
• 为找到关节点，在图上执行一个深度优先遍历，在遍历过程中，对每个顶点维护两个标号：。仅仅是，对于初始化为，在后续遍历中国更新为下面几个值中的最小值：
  • ；
  • ：对于每个顶点，是一条回边；
  • ，在过程中的每条边。
• 关节点的确定如下：
  • 根是一个关节点，当且仅当在深度优先搜索树中，它有两个或更多的儿子；
  • 根以外的节点是一个关节点当且仅当有一个儿子，满足；（只要存在一个就行）

ARTICPOINTS

输入：连通无向图。

输出：包含的所有可能关节点数组。

设s为起始顶点
for each v in V
    visited[v] <- false
end for
predfn <- 0; count <- 0; rootdegree <- 0
dfs(s)

过程： dfs(v)
visited[v] <- true; artpoint <- false; predfn <- predfn + 1
alpha[v] <- predfn; beta[v] <- alpha[v] #初始化alpha，beta
for each (v,w) in E
    if (v,w)是树边 then
        dfs(w)
        #下面的操作发生在w回退到v时
        if v = s then #如果是根节点，用rootdegree判断根节点是否有两个以上的儿子
            rootdegree <- rootdegree + 1
            if rootdegree = 2 then artpoint <- true
        else #不是根节点，则找最小值
            beta[v] <- min{beta[v], beta[w]}
            if beta[w] >= alpha[v] then artpoint <- true
        end if
    else if (v,w)是回边 then beta[v] <- min{beta[v], alpha[w]}
    else do noting
    end if
 end for
if artpoint then #记录关节点
    count <- count + 1
    A[count] <- v
end if

• zGJLCR.png
  zGJxKK.png

• 结合深度有限搜索树判断关节点

  1. 深度优先生成树的根是关节点的充要条件是它至少有两个子女；
  2. 任何其它顶点u是关节点的充要条件是u至少有一个子女w，使得经过只由w，w的后代以及一条回边构成的路径不可能到达u的祖先，因为删除顶点u及其关联的边将使w及其后代与u的祖先断开联系。

强连通分支

• 如果一个有向图，强连通分支是它的顶点的一个极大子集，在该集中，任意两个顶点直接都存在一条路径。通俗地理解，把顶点看成一个房子，强连通分支集合里可以从任意一个房子走到另一个房子。

STRONGCONNECTCOMP

输入：有向图G=(V,E)。

输出：G中的强连通分支。

在图G执行深度优先搜索，对每个顶点赋给相应的postdfn。
颠倒图G中边的方向，构造新的图G'。
从具有最好postdfn的顶点开始，在G'上进行深度优先搜索，如果DFS不能访问所有顶点，则找次大的postdfn顶点开始DFS。
所得到的每一棵树都是一个强连通分支。

zGt9yV.md.png

广度优先搜索BFS

• 所谓广度，形象地理解为一圈一圈的访问，从起始点往外扩散，利用队列实现。

  zGtuy6.md.png

• 对于也有广度优先搜索树、树边、回边、前向边、横跨边