2010JSOI B 层次函授第四讲
三. 图的遍历
从图中某一顶点出发系统地访问图中所有顶点,使每个顶点恰好被访问一次,这种运
算操作被称为图的遍历。为了避免重复访问某个顶点,可以设一个标志数组 visited[i],
未访问时值为 false,访问一次后就改为 true。
1. 深度优先遍历
从图中某个顶点 V
i
出发,访问此顶点并作已访问标记,然后从 V
i
的一个未被访问过的
邻接点 V
j
出发再进行深度优先遍历,当 V
i
的所有邻接点都被访问过时,则退回到上一个顶
点 V
k
,再从 V
k
的另一个未被访问过的邻接点出发进行深度优先遍历,直至图中所有顶点
都 被 访 问 到 为 止 。 如 下 面 的 左 图 从 顶 点 a 出 发 , 进 行 深 度 优 先 遍 历 的 结 果 为 :
a , b , c , d , e , g , f ; 右 图 从 V
1
出 发 进 行 深 度 优 先 遍 历 的 结 果 为 :
V
1
,V
2
,V
4
,V
8
,V
5
,V
3
,V
6
,V
7
。
2. 广度优先遍历
从图中某个顶点 V
0
出发,访问此顶点,然后依次访问与 V
0
邻接的、未被访问过的所
有顶点,然后再分别从这些顶点出发进行广度优先遍历,直到图中所有被访问过的顶点的
相邻顶点都被访问到。若此时图中还有顶点尚未被访问,则另选图中一个未被访问过的顶
点作为起点,重复上述过程,直到图中所有顶点都被访问到为止。如上面的左图从顶点 a
出发,进行广度优先遍历的结果为:a,b,d,e,f,c,g;右图从顶点 V
1
出发,进行广
度优先遍历的结果为:V
1
,V
2
,V
3
,V
4
,V
5
,V
6
,V
7
,V
8
。
两种遍历方法相比,深度优先遍历实际上是尽可能地走“顶点表”;而广度优先遍历是
尽可能沿顶点的“边表”进行访问,然后再沿边表对应顶点的边表进行访问,因此,有关边
表的顶点需要保存(用队列,先进先出),以便进一步进行广度优先遍历。
四. 图中的经典算法
1. 求最小生成树
如果图 G=(V,E)是一个连通的无向图,则把它的全部顶点 V 和一部分边 E’构成一
个子图 G’,即 G’=(V, E’),且边集 E’能将图中所有顶点连通又不形成回路,则称子
图 G’是图 G 的一棵生成树。同一个图可以有不同的生成树,但可以证明:n 个顶点的连通
图的生成树必定含有 n-1 条边。对于加权连通图(连通网),生成树的权即为生成树中所
有边上的权值总和,权值最小的生成树称为图的最小生成树。
求图的最小生成树具有很高的实际应用价值,比如要在若干个城市之间建一个交通网,
要求各个城市都能到达且造价最低,这就是一个典型的最小生成树问题。那么如何求(最
小)生成树呢?求(最小)生成树可以从某个顶点采用深度优先遍历的方法,也可采用广
度优先遍历的方法,分别称为深度优先生成树和广度优先生成树。
4/18