第8章图第13讲-小结(2)

1、 生成树和最小生成树带权连通图带权连通图生成树生成树极小连通子图极小连通子图最小生成树最小生成树所有边权值和最小所有边权值和最小1/19深度优先遍历深度优先遍历 深度优先生成树深度优先生成树广度优先遍历广度优先遍历 广度优先生成树广度优先生成树广度优先生成树高度广度优先生成树高度 深深度优先生成树高度度优先生成树高度2/19若一个具有若一个具有n个顶点和个顶点和e条边的无向图是一个森条边的无向图是一个森林（林（ne），则该森林必有（），则该森林必有（ ）棵树。）棵树。 A.e B.nC.n- -eD.1设该森林有设该森林有m棵树，节点个数分别为棵树，节点个数分别为n1、n2、nm总节点数总节点

2、数n = n1 + n2 + + nm第第i棵树的边数棵树的边数=ni- -1（可以看成自己的生成树）（可以看成自己的生成树）总边数总边数 = (n1- -1)+(n2- -1)+(nm- -1) = n- -m = e，所以，所以m = n- -e C3/19起点起点v 所有顶点分为所有顶点分为U（vU）和）和V-U每次选择这两个集合之间的最小边每次选择这两个集合之间的最小边O(n2)Kruskal算法算法Prim算法算法将边按权值递增排列将边按权值递增排列每次选择权值小并且不构成回路的边每次选择权值小并且不构成回路的边O(elog2e)4/19 一个带权连通图中所有权值最小的边一定会出一个

3、带权连通图中所有权值最小的边一定会出现在所有的最小生成树中现在所有的最小生成树中？不一定！不一定！120311121201113Kruskal5/19对某个带权连通图构造最小生成树，以下说法中正确的是（）。对某个带权连通图构造最小生成树，以下说法中正确的是（）。.该图的所有最小生成树的总代价一定是唯一的该图的所有最小生成树的总代价一定是唯一的.该图的最小生成树是唯一的该图的最小生成树是唯一的.用用Prim算法从不同顶点开始构造的所有最小生成树一定相同算法从不同顶点开始构造的所有最小生成树一定相同.使用使用Prim和和Kruskal算法得到的最小生成树总不相同算法得到的最小生成树总不相同 A.仅

4、仅 B.仅仅C.仅仅、仅仅、 A6/19 最 短 路 径源点源点v加入加入S，U=V-S初始化：初始化： 若若v i有边：有边： disti=(v，i)权值权值 pathi=v否则：否则： disti= pathi=-1从从U中选择中选择dist最最小的顶点小的顶点u考察所有从考察所有从u有出边有出边的顶点的顶点j，调整：，调整：若若distu+(u，j)权值权值distj ： distj= distu+(u，j)权值权值 pathj=u否则：否则： 不变不变直到直到S=V 时间复杂度：时间复杂度：O(n2)7/19Dijkstra算法是（算法是（ ）方法求出图中从源点到其余顶点最短路径的。）

5、方法求出图中从源点到其余顶点最短路径的。A.按长度递减的顺序求出图的某顶点到其余顶点的最短路径按长度递减的顺序求出图的某顶点到其余顶点的最短路径B.按长度递增的顺序求出图的某顶点到其余顶点的最短路径按长度递增的顺序求出图的某顶点到其余顶点的最短路径C.通过深度优先遍历求出图中某顶点到其余顶点的最短路径通过深度优先遍历求出图中某顶点到其余顶点的最短路径D.通过广度优先遍历求出图中某顶点到其余顶点的最短路径通过广度优先遍历求出图中某顶点到其余顶点的最短路径 S加入加入S集合的顶点：集合的顶点：最短路径不再改变越后加入的顶点，dist越长8/19以下叙述正确的是（以下叙述正确的是（ ）。）。A. 最

6、短路径一定是简单路径最短路径一定是简单路径B. Dijkstra算法不适合有回路的带权图求最短路径算法不适合有回路的带权图求最短路径C. Dijkstra算法不适合求任意两个顶点的最短路径算法不适合求任意两个顶点的最短路径D. Floyd算法求两个顶点的最短路径时，算法求两个顶点的最短路径时，pathk-1一定是一定是pathk的子集的子集 9/19ij0n-1迭代迭代 时间复杂度：时间复杂度：O(n3)10/19 Dijkstra算法用于求单源最短路径，为了求一个图中算法用于求单源最短路径，为了求一个图中所所有顶点对有顶点对之间的最短路径，可以以每个顶点作为起点调用之间的最短路径，可以以每个

7、顶点作为起点调用Dijkstra算法，算法，Floyd算法和这种算法相比，有什么优势？算法和这种算法相比，有什么优势？从每个顶点调用从每个顶点调用Dijkstra算法算法Floyd算法算法时间复杂度：时间复杂度：O(n3)从每个顶点调用从每个顶点调用Dijkstra算法：独立算法：独立Floyd算法：算法：A共享共享Floyd算法性能更好11/19 设下图中的顶点表示村庄，有向边代表交通设下图中的顶点表示村庄，有向边代表交通路线，若要建立一家医院，试问建在路线，若要建立一家医院，试问建在哪一个村庄哪一个村庄能使各村庄总体交通代价最小。能使各村庄总体交通代价最小。0331212121313445

8、315612/19利用利用Floyd算法任意两个顶点之间的最短路径长度算法任意两个顶点之间的最短路径长度036207220121743412029165811012184161304A求得每对村庄之间的最少交通代价求得每对村庄之间的最少交通代价医院建在的医院建在的村庄村庄各村庄往返总的交通代各村庄往返总的交通代价价012+16+4+7+13+16+4+18=90113+29+17+20+12+8+5=115216+11+12+6+16+29+12+34=13634+8+12+3+4+17+12+22=82418+5+34+22+7+20+6+3+0=115把医院建在村庄3时总体交通代价最少。1

9、3/19 拓 扑 排 序找入度为找入度为0的顶点的顶点输出该顶点，删除从输出该顶点，删除从它出发的所有出边它出发的所有出边成功：产生所有顶点的拓扑序列：产生所有顶点的拓扑序列不成功：不能产生所有顶点的拓扑序列：不能产生所有顶点的拓扑序列14/19 若一个有向图中的顶点不能排成一个拓扑序列，若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有向图（则可断定该有向图（ ） A.是个有根有向图是个有根有向图 B.是个强连通图是个强连通图 C.含有多个入度为含有多个入度为0的顶点的顶点 D.含有顶点数目大于含有顶点数目大于1的强连通分量的强连通分量 不能排成一个拓扑序列不能排成一个拓扑序列有回路有回

10、路顶点数大于顶点数大于1的强连通分量的强连通分量15/19 若用邻接矩阵存储有向图，矩阵中主对角线以下的元若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（素均为零，则关于该图拓扑序列的结论是（ ）。）。 A.存在，且唯一存在，且唯一B.存在、且不唯一存在、且不唯一 C.存在，可能不唯一存在，可能不唯一D.无法确定是否存在无法确定是否存在有向图：顶点有向图：顶点i j（ij）可能有边，而顶点）可能有边，而顶点j i一定没有边一定没有边 该有向图中一定没有回路该有向图中一定没有回路可以产生拓扑序列，但拓扑序列不一定唯一可以产生拓扑序列，但拓扑序列不一定唯一16/19 关 键 路 径对事件（顶点）进行拓扑排序对事件（顶点）进行拓扑排序按按拓扑序列拓扑序列求所有事件的最早开始时间求所有事件的最早开始时间按按拓扑逆序列拓扑逆序列求所有事件的最迟开始时间求所有事件的最迟开始时间求所有活动（边）的最早开始时间求所有活动（边）的最早开始时间求所有活动的最迟开始时间求所有活动的最迟开始时间关键活动：最早开始时间关键活动：最早开始时间=最迟开始时间最迟开始时间17/19以下对于以下对于AOE网的叙述中，网的叙述中，错误错误的是（的是（ ）。）。A.在在AOE网中可能