图的遍历和生成树

7.3　图的遍历和生成树

图的遍历是指从图的任意指定顶点出发,按照某种规则访问图中的所有顶点,并且每个顶点仅被访问一次而得到的序列。图的遍历算法是求解图的连通性、拓扑排序和求关键路径等算法的基础。图的遍历方法有深度优先遍历和广度优先遍历两种。

7.3.1　深度优先遍历

深度优先遍历（DFS）类似树的前序遍历,其遍历过程如下。

（1）初始状态是图中所有顶点都未被访问,选定某一顶点v₀,访问v₀之后,由v₀出发,选取一个与v₀邻接且没有被访问的任一点w₁进行访问。

（2）再由w₁出发,选取一个与w₁邻接且没有被访问的任一点w₂进行访问。

（3）再由w₂出发,依此类推,重复上述过程,直至某顶点w_i的所有邻接点都被访问过,则退回一步找顶点w_i－1尚未被访问的邻接点。

（4）如果顶点w_i－1存在尚未被访问过的邻接点,则访问此邻接点,然后再从该顶点出发,按深度优先进行遍历。如果顶点w_i－1没有尚未被访问的邻接点,则回退一步再进行搜索,重复上述过程,一直到所有和顶点v₀有路径相通的顶点都被访问过为止。

（5）如果图中还有顶点未被访问,即该图为非连通图,则选择图中一个未被访问的顶点作为起点,重复上述过程,直至图中所有的顶点都被访问过为止。

按照上述思想对如图7－22所示的无向图进行深度优先遍历。

（1）初始状态所有顶点未被访问,设定v₁是出发点,首先访问v₁。

（2）v₁的两个邻接点v₂、v₃均末被访问过,选择v₂作为新的出发点,访问v₂。

（3）v₂的邻接点有v₁、v₄和v₅,其中v₁已被访问过,而v₄、v₅尚未被访问过,选择v₄作为新的出发点,访问v₄。

（4）v₄的邻接点有v₂和v₈,其中v₂已被访问过,而v₈尚未被访问过,选择v₈作为新的出发点,访问v₈。

（5）v₈的邻接点有v₄、v₅、v₆和v₇,其中v₄已被访问过,而v₅、v₆和v₇尚未被访问过,选择v₅作为新的出发点,访问v₅。

（6）v₅的邻接点有v₂和v₈,均已被访问过,遍历退回到v₈,访问v₈的另一个邻接点v₆。

（7）v₆的邻接点有v₃和v₈,其中v₈已被访问过,而v₃尚未被访问过,选择v₃作为新的出发点,访问v₃。

（8）v₃的邻接点有v₁、v₆和v₇,其中v₁和v₆已被访问过,而v₇尚未被访问过,选择v₇作为新的出发点,访问v₇。

最后得到的顶点的访问序列为:v₁→v₂→v₄→v₈→v₅→v₆→v₃→v₇。

图7－22　无向图的深度优先遍历

遍历过程中的回退也称为回溯。回溯时沿着与访问的顺序相反的顺序,当回溯到仍有未被访问邻接点的一个顶点时,把这个点作为起始点,再找一条路径继续向前搜索。因此,图的深度优先搜索遍历过程是个递归过程。

在图的遍历过程中,为了区分图中顶点是否被访问过,需要设置一个辅助数组visited[],长度为图的顶点数,初值为0或假,当访问了某顶点v_i后,便修改visited[i]为1或真。下面的程序实现了图的深度优先遍历的递归算法。

firstadj（g,v）函数的功能为求顶点v在图G中的第一个邻接点,nextadj（g,v,w）函数的功能是求顶点v在图G中相对于v的下一个邻接点。下面分别用邻接矩阵和邻接表两种存储结构来实现图的深度优先遍历。

//邻接矩阵的深度遍历操作

voiddfstraverse(mgraphg)

邻接矩阵是二维数组,要查找某个顶点的邻接点需要访问矩阵中的所有元素,时间复杂度为O（n²）的时间。在邻接表中找某个顶点的邻接点所需的时间取决于顶点和边的数量,所以时间复杂度是O（n＋e）。显然,对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。

7.3.2　广度优先遍历

广度优先遍历（BFS）类似于树的按层遍历,其遍历过程如下。

（1）初始状态是图中所有顶点都未被访问,选定某个顶点v₀,访问v₀。

（2）从v₀出发,依次访问v₀的全部邻接点w₁,w₂,…,w_d。

（3）再依次访问w₁,w₂,…,w_d顶点中尚未被访问过的全部邻接点。

（4）再从这些被访问过的顶点出发,逐一访问与它们尚未被访问过的全部邻接点。

（5）依此类推,直到所有已被访问的顶点的全部邻接点都被访问到为止。

（6）如果此时图中还有未被访问的顶点（非连通图）,则选择图中某个尚未被访问的顶点作为出发点,重复上述遍历过程,直至图中所有顶点都被访问到为止。按照上述思想对图7－23所示的无向连通图进行广度优先遍历。

图7－23　无向图的广度优先遍历

（1）初始状态为所有顶点都未被访问,选定顶点v₁为出发点,访问v₁；

（2）v₁有两个邻接点v₂和v₃,都未被访问过,依次访问v₂和v₃；

（3）v₂有三个邻接点v₁、v₄和v₅,v₁已经被访问过,v₄和v₅未被访问,依次访问v₄和v₅；

（4）v₃有三个邻接点v₁、v₆和v₇,v₁已经被访问过,v₆和v₇未被访问,依次访问v₆和v₇；

（5）v₄有两个邻接点v₂和v₈,v₂已被访问过,v₈未被访问,访问v₈；

（6）v₅、v₆、v₇和v₈的邻接点都被访问过,遍历结束。

顶点访问顺序是:v₁→v₂→v₃→v₄→v₅→v₆→v₇→v₈。

在图的广度优先遍历过程中,若顶点w₁在顶点w₂之前访问过,则w₁的邻接点也将在w₂的邻接点之前访问。因此,需要记录顶点被访问的顺序,可以采用先进先出的队列来依次记录被访问的顶点。

采用邻接矩阵作为存储结构,图的广度优先遍历程序如下。

对于邻接表的广度优先遍历,其程序与邻接矩阵差异不大,具体程序如下。

图的深度优先遍历与广度优先遍历算法的时间复杂度是一样的,但对顶点的访问顺序不同。

7.3.3　生成树和生成森林

深度优先遍历和广度优先遍历都可以用于测试无向图的连通性。如果无向图是连通的,从无向图中的任意顶点出发进行深度优先遍历或广度优先遍历都可以访问到每一个结点。访问的结果是一棵深度/广度优先生成树。如果无向图是非连通图的,从图中某顶点v₀出发遍历图,不能访问到图中的所有顶点,而只能访问到包含v₀的最大连通子图（连通分量）中的所有顶点。若从非连通图中的每个连通分量中的某个顶点出发遍历图,则可求出无向图的所有连通分量,构成深度/广度优先生成森林。求图的连通分量实际是图的遍历的一种应用。

图7－24所示为从连通图G₇的顶点v₀出发分别进行深度优先遍历和广度优先遍历,得到的生成树。

图7－24　连通图的生成树

图7－25所示为非连通图和深度优先生成森林,森林中每棵树是其连通分量的生成树。

图7－25　非连通图的深度优先生成森林

7.3.4　双向连通图

对无向图进行深度优先或广度优先遍历,可以判断无向图是否连通。如果从某个顶点出发进行遍历,遍历结束后,还有未访问到的顶点,说明该无向图不是连通图,否则就是连通图。对未访问到的顶点出发继续进行深度或广度遍历,可得到无向非连通图的所有连通分支。

一个无向连通图,若去掉任一点或任一边,该图仍连通,那么该图是一个双向连通图。一个无向连通图,若去掉一点或一边后,图不连通了,则该图不是双向连通图。去掉的这一点称为关节点（割点）,如果删除它及其关联的边后,得到的新图至少包含两个连通分支。如图7－26所示的无向图中,顶点A就是一个关节点。无向连通图的双连通子图是无向图的最大双连通分支。在深度优先遍历时,必定要经过图的关节点,并生成一棵深度优先遍历树,利用该树可以求解无向连通图的双连通分支。

图7－26　非双向连通图

以图7－26所示的无向图为例,如果从顶点A开始深度遍历,得到如下一棵树,如图7－27所示。

该树中,A是树根,顶点旁的编号是深度遍历访问顶点的顺序,虚线边是图中深度遍历没有访问到的边,称为非树边或回退边,黑色带箭头的边是树边。对无向图进行深度优先遍历得到的树是一棵开放树,如果在其中添加一条回退边,就会形成环,该环路或扩大连通分量的范围,或者导致新的连通分量产生。如果要在这棵树中确定哪些点是关节点,则该结点需符合以下两个特性。

（1）若生成树的根有两棵或两棵以上子树,则此根结点必为关节点。因为图中不存在连接不同子树中顶点的边,因此,若删去根顶点,生成树变成生成森林。如图7－27所示树中的顶点A。

图7－27　无向图的深度优先遍历树

（2）若生成树中非叶子顶点v,并且v不是树根,则从其某个孩子顶点w出发,不能通过w的后继顶点组成的路径和一条回退边到v的任意一个祖先顶点,此时v是一个关节点。也就是说,顶点v的某棵子树的根和子树中的其他顶点均没有指向v的祖先的回退边,则v是关节点。因为删去v,则其子树和图的其他部分被分割开来。如图7－27所示树中顶点C,它的孩子结点只有顶点F,而F能到达的最低层顶点是C,无法访问到C的祖先顶点,因此C是一个关节点。

基于关节点的特点,给每个顶点定义一个low值,low（u）表示从u出发,经过一条其后继顶点组成的路径和回退边,所能到达的最小深度的顶点的编号。对于每个顶点u,low（u）的定义如下。

low（u）＝min{dfn（u）,min{low（w）｜w是u的孩子},min{dfn（w）,｜（u,w）是一条回退边}}

其中,dfn（u）是深度优先遍历过程中对顶点的编号。

在对图进行深度优先遍历过程中计算出dfn值和low值,如果发现顶点u有一个孩子结点w,使得low（w）≥dfn（u）,就说明它的后代无法到达比u深度更浅的顶点,即无法到达u的祖先,那么u就是个关节点。

求无向图的双连通分量的算法描述如下。

（1）计算图中各个顶点的深度优先遍历编号。对图进行深度优先遍历,计算每个结点v的编号dnf（v）,形成生成树S＝（V,T）。

（2）计算low（v）。在深度优先遍历生成树上按后根顺序进行计算每个顶点v的low（v）,low（v）取以下三个结点中的最小者。

①dfn（v）。

②dfn（w）,凡是有回退边（v,w）的任何结点w。

③low（y）,对v的任何孩子y。

（3）求关节点。树根是关节点,当且仅当它有两个或两个以上的孩子时。非树根结点v是关节点,当且仅当v有某个孩子y,使得low[y]≥dnf[v]时。