第15讲图的遍历

1、 一、图的遍历（深度、广度）一、图的遍历（深度、广度） 二、最小生成树二、最小生成树 三、三、普里姆算法普里姆算法 四、克鲁斯卡尔算法四、克鲁斯卡尔算法难点难点从图的某顶点出发，访问图中所从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。有顶点，并且每个顶点仅访问一次。在图中，访问部分顶点后，可能又沿着其他在图中，访问部分顶点后，可能又沿着其他边回到已被访问过的顶点。边回到已被访问过的顶点。为保证为保证每一个顶点只被访问一次每一个顶点只被访问一次，必须对顶，必须对顶点进行标记，一般用一个标识域点进行标记，一般用一个标识域 tagtag作为对顶点的标作为对顶点的标记，当顶点记，当顶点v

2、i vi未被访问，未被访问，tagtag初始值为初始值为 UNVISITEDUNVISITED；当当vi vi已被访问，则已被访问，则tagtag值为值为 VISITEDVISITED。 图的遍历与图的遍历与树的遍历有什么不同树的遍历有什么不同 有两种遍历方法有两种遍历方法（它们对无向图，有向图都适用）它们对无向图，有向图都适用） 深度优先遍历深度优先遍历 Depth_FirstDepth_First Search Search 广度优先遍历广度优先遍历 Breadth_FirstBreadth_First Search Search算法：算法：从图中某顶点从图中某顶点v v出发：出发： （1

3、 1）访问顶点）访问顶点v v；（2 2）依次从）依次从v v的未被访问的邻接点出发，继续对图进的未被访问的邻接点出发，继续对图进行深度优先遍历；行深度优先遍历；深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5 V5深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5V8 V8深一层递归深一层递归递归返回递归返回深

4、度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1V2 V2V4 V4V5V8深一层递归深一层递归递归返回递归返回深度优先遍历序列深度优先遍历序列?入栈序列入栈序列?出栈序列出栈序列?V1V3V2V4V5V6V7V8 V1遍历序列：遍历序列：V1 V7V2V4V5V8V3 V3V6 V6V7图的深度优先遍历算法图的深度优先遍历算法图的深度优先遍历算法图的深度优先遍历算法 A A H H G G F F E E D D C C B B图的深度优先遍历算法图的深度优先遍历算法 0 0 1 1 2 2 3 3 4 4 5

5、 5 6 6 7 7A AB BC CD DE EF FG GH H1 12 26 67 73 30 01 11 10 04 45 53 36 62 25 52 23 34 4 图中有图中有 n 个顶点，个顶点，e 条边。条边。 如果用如果用邻接表邻接表表示图，沿表示图，沿adjLink链到链到next 链链可以找到某个顶点可以找到某个顶点 v 的所有邻接顶点的所有邻接顶点 w。由于。由于总共有总共有 2e 个边结点，所以扫描边的时间为个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问。而且对所有顶点递归访问1次，所以遍次，所以遍历图的时间复杂性为历图的时间复杂性为O(n+e)。 如

6、果用如果用邻接矩阵邻接矩阵表示图，则查找每一个顶点的表示图，则查找每一个顶点的所有的边，所需时间为所有的边，所需时间为O(n)，则遍历图中所有，则遍历图中所有的顶点所需的时间为的顶点所需的时间为O(n2)。 有向图的邻接表如下，有向图的邻接表如下，要求（要求（1）画出其邻）画出其邻接矩阵存储；（接矩阵存储；（2）写出图的所有强连同写出图的所有强连同分量；（分量；（3）写出顶）写出顶点点a到顶点到顶点i的全部简的全部简单路径；（单路径；（4）写出）写出以以A为出发点开始深为出发点开始深度优先遍历得到的顶度优先遍历得到的顶点序列。点序列。 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8

7、 8 9 9A AB BE ED DH HI IC CG GF F2 27 76 63 34 45 52 28 87 73 39 96 6 已知一个有向图如下，则从顶点已知一个有向图如下，则从顶点a出发进行深出发进行深度优先遍历，不可能够得到的度优先遍历，不可能够得到的DFS序列为？序列为？ A adbefc B adcefb C adcbfe D adefbcacefdb算法：算法：从图中某未访问过的顶点从图中某未访问过的顶点vi出发：出发：（1）访问顶点）访问顶点vi ；（2）访问）访问 vi 的所有未被访问的邻接点的所有未被访问的邻接点w1 ,w2 , wk ；（3）依次从这些邻接点出发

8、，访问它们的所有未被访问）依次从这些邻接点出发，访问它们的所有未被访问的邻接点的邻接点;依此类推，直到图中所有访问过的顶点的依此类推，直到图中所有访问过的顶点的邻接点都被访问；邻接点都被访问；（类似于树的层次遍历）（类似于树的层次遍历）为实现为实现(3)(3)，需要保存在步骤，需要保存在步骤(2)(2)中访问的顶点，而且中访问的顶点，而且访问访问这些顶点这些顶点邻接点邻接点的顺序为：先保存的顶点，其邻接点先被的顺序为：先保存的顶点，其邻接点先被访问。访问。在广度优先遍历算法中，在广度优先遍历算法中，需设置一需设置一队列队列Q Q，保存已访问的顶点，保存已访问的顶点，并控制遍历顶点的顺序。并控制

9、遍历顶点的顺序。 V1V1 V8V8 V7V7 V6V6 V5V5 V4V4 V3V3 V2V2广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V1广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V2V3V3广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V3V3V4V4V5V5广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列?

10、V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V3V4V4V5V5V6V6V7V7广度优先遍历序列广度优先遍历序列?入队序列入队序列?出队序列出队序列? V1V3V2V4V5V6V7V8遍历序列：遍历序列：V1V2V3V4V5V5V6V6V7V7V8V8template void BFSTraverse(const AdjListDirGraph &g, void (*Visit)(const ElemType &)int v;for (v = 0; v g.GetVexNum(); v+)g.SetTag(v, UNVISITED); for (v = 0; v

11、 g.GetVexNum(); v+)if (g.GetTag(v) = UNVISITED) BFS(g, v , Visit);图的广度优先遍历算法图的广度优先遍历算法template void BFS(const AdjListDirGraph &g, int v, void (*Visit)(const ElemType &)g.SetTag(v, VISITED);ElemType e;g.GetElem(v, e);Visit(e);LinkQueue q;q.InQueue(v);图的广度优先遍历算法图的广度优先遍历算法while (!q.Empty()/ 队列队

12、列q非空非空, 进行循环进行循环int u, w;q.OutQueue(u);for (w = g.FirstAdjVex(v); w = 0; w = g.NextAdjVex(v, w)if (g.GetTag(w) = UNVISITED)g.SetTag(w, VISITED);g.GetElem(w, e);Visit(e);q.InQueue(w);图的广度优先遍历算法图的广度优先遍历算法 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4 V0V0 V2V2 V3V3 V1V1 V5V5 V4V4深度优先遍历深度优先遍历广度优先遍历广度优先遍历两种遍历两种遍历的比较的比较

13、两者遍历的时间复杂度相同，不同两者遍历的时间复杂度相同，不同之处仅仅在于对顶点访问的顺序。之处仅仅在于对顶点访问的顺序。无向图的连通分量和生成树无向图的连通分量和生成树 生成树生成树是一个连通图是一个连通图G 的一个极小的连通子的一个极小的连通子图。包含图图。包含图G 的所有顶点，但只有的所有顶点，但只有n-1 条边，并且条边，并且是连通的。是连通的。 生成树可由遍历过程中所经过的边组成。深生成树可由遍历过程中所经过的边组成。深度优先遍历得到的生成树称为度优先遍历得到的生成树称为深度优先生成树深度优先生成树；广；广度优先遍历得到的生成树称为度优先遍历得到的生成树称为广度优先生成树广度优先生成树

14、。 生成森林生成森林：非连通图每个连通分量的生成树：非连通图每个连通分量的生成树一起组成非连通图的生成森林。一起组成非连通图的生成森林。V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8深度优先生成树深度优先生成树V1V2V4V5V3V7V6V8广度优先生成树广度优先生成树V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林例例 说明说明 一个图可以有

15、许多棵不同的生成树一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点：所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图生成树是图的极小连通子图 一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1条边条边 生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路 含含n个顶点个顶点n-1条边的图不一定是生成树条边的图不一定是生成树GHKI 要在要在 n n个城市间建立交通网，个城市间建立交通网，要考虑的问题如何在保

16、证要考虑的问题如何在保证n n点连通点连通的前题下最节省经费的前题下最节省经费? V2V2V0V0V3V3V5V5V4V4V1V13 38 86 62 21 18 86 66 65 58 8例例 求解求解: 连通连通6 6个城市且代价个城市且代价最小的交通线路最小的交通线路? 如何求连通图的如何求连通图的最小生成树最小生成树? 若有一个连通的无向图若有一个连通的无向图G，有，有n个顶点，个顶点，并且它的边是有权值的。在并且它的边是有权值的。在G上构造生成树上构造生成树 G ,最小生成树最小生成树是是 n-1 条边的权值之和最小条边的权值之和最小的的 G 。 普里姆算法普里姆算法 Prim 克鲁

17、斯卡尔算法克鲁斯卡尔算法 Kruskal例例1654328613688526131163151643152116432152616543215263 普里姆算法普里姆算法 Primq 设设N=（V，E）为一个具有）为一个具有n个顶点的带权的连通网个顶点的带权的连通网络，络，T=（U，TE）为构造的生成树。）为构造的生成树。 (1) 初始时，初始时，U= U0 ，TE= ； (2) 在所有在所有u U 、v V-U的边的边(u,v) E中选择一条权中选择一条权值最小的边值最小的边(u0,v0)； (3) (u0,v0)加入集合加入集合TE，同时将，同时将v0加入加入U； (4) 重复重复(2)、

18、(3)，直到，直到U=V为止；为止；abcdegf195141827168213ae12dcbgf7148531621所得生成树权值和所得生成树权值和= 14+8+3+5+16+21 = 67再如：再如：KruskalKruskal的基本思想：的基本思想： 设有一个有设有一个有n n个顶点的连通网络个顶点的连通网络 N=V,E, N=V,E, 最初先构造一最初先构造一个只有个只有n n个顶点个顶点, , 没有边的非连通图没有边的非连通图 T=V,T=V, , 图中每个顶图中每个顶点自成一个连通分量。点自成一个连通分量。 在在E E中选到一条具有最小权值的边中选到一条具有最小权值的边, , 若该

19、边的两个顶点若该边的两个顶点落落在不同的连通分量在不同的连通分量上，则将此边加入到上，则将此边加入到 T T 中中; ; 否则将此边舍否则将此边舍去，重新选择一条权值最小的边。去，重新选择一条权值最小的边。 如此重复下去如此重复下去, , 直到所有顶点在直到所有顶点在同一个连通分量同一个连通分量上为止。上为止。5046132281025142422161812原图5046132(a)105046132(b)504612281025142422161812原图3(f)50461321014221612504613210141612(e)5046121025142216123(g)10125046

20、132(c)5046132101412(d)1. 初始化：初始化：U=V； TE= ； 2. 循环直到循环直到T中的连通分量个数为中的连通分量个数为1 2.1 在在E中寻找最短边中寻找最短边( (u，v) ); 2.2 如果顶点如果顶点u、v位于位于T的两个不同连通分量，则的两个不同连通分量，则 2.2.1 将边将边( (u，v) )并入并入TE； 2.2.2 将这两个连通分量合为一个；将这两个连通分量合为一个； 2.3 在在E中标记边中标记边( (u，v) )，使得，使得( (u，v) )不参加后续不参加后续最短边的选取；最短边的选取；【ACM】【ZOJ1406】最小生成树问题最小生成树问题

21、【问题描述问题描述】如上图所示，给出结点数量如上图所示，给出结点数量N，以及每个结点到相邻，以及每个结点到相邻结点的距离，要求给出一条最短连通路径，连通所有结点的距离，要求给出一条最短连通路径，连通所有结点（结点的字母不重复，个数不超过结点（结点的字母不重复，个数不超过26个）。个）。 根据上图我们可以给出如下一组数据：根据上图我们可以给出如下一组数据： 9 A 2 B 12 I 25 B 3 C 10 H 40 I 8 C 2 D 18 G 55 D 1 E 44 E 2 F 60 G 38 F 0 G 1 H 35 H 1 I 35 第一行的第一行的9表示有表示有9个结点，接下来共个结点，

22、接下来共8行数据，每行行数据，每行数据给出该结点的名称数据给出该结点的名称name，和相邻结点数，和相邻结点数num，以，以及与相邻结点及与相邻结点X之间的距离之间的距离Y。 不难发现，每行结点只给出了结点名称大于该结点的不难发现，每行结点只给出了结点名称大于该结点的相邻结点的距离。比如相邻结点的距离。比如B与与A相邻，且距离为相邻，且距离为12。在第一。在第一行行A“结点信息表结点信息表”中给出了中给出了A到到B的距离的距离12，但在第二行，但在第二行B“结点信息表结点信息表”中就不必给出小于字母中就不必给出小于字母B的的A结点的信息结点的信息（为了避免数据冗余）。所以最后一个结点（为了避免数据冗余）。所以最后一个结点I，没有比它，没有比它字母再大的结点，故省略该行。字母再大的结点，故省略该行。 要求最后得出一条最短连通路径，把该路径长度输出，要求最后得出一条最短连通路径，把该路径长度输出，在本例中路