《第11周图（下）第8讲-本周小结.pdf》由会员分享，可在线阅读，更多相关《第11周图（下）第8讲-本周小结.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1生成树和最小生成树 带权连通图带权连通图生成树生成树 极小连通子图极小连通子图 最小生成树最小生成树 所有边权值和最小所有边权值和最小 1/18 深度优先遍历深度优先遍历 深度优先生成树深度优先生成树 广度优先遍历广度优先遍历 广度优先生成树广度优先生成树 广度优先生成树高度广度优先生成树高度 深深度优先生成树高度度优先生成树高度 2/18 若一个具有若一个具有n个顶点和个顶点和e条边的无向图是一个森林条边的无向图是一个森林 （ne），则该森林必有（），则该森林必有（）棵树。）棵树。 A.eB.nC.n- -eD.1 设该森林有设该森林有m棵树，节点个数分别为棵树，节点个数分别为n1、n2、
2、nm 总节点数总节点数n = n1 + n2 + + nm 第第i棵树的边数棵树的边数=ni- -1（可以看成自己的生成树）（可以看成自己的生成树） 总边数总边数 = (n1- -1)+(n2- -1)+(nm- -1) = n- -m = e，所以，所以m = n- -e C 3/18 起点起点v 所有顶点分为所有顶点分为U（v U）和）和V-U 每次选择这两个集合之间的最小边每次选择这两个集合之间的最小边 O(n2) Kruskal算法算法 Prim算法算法 将边按权值递增排列将边按权值递增排列 每次选择权值小并且不构成回路的边每次选择权值小并且不构成回路的边 O(elog2e) 4/18
3、 一个带权连通图中所有权值最小的边一定一个带权连通图中所有权值最小的边一定 会出现在所有的最小生成树中会出现在所有的最小生成树中？ 不一定！不一定！ 1 2 0 3 1 1 1 2 1 2 0 1 1 1 3 Kruskal 5/18 对某个带权连通图构造最小生成树，以下说法中正确的是（）。对某个带权连通图构造最小生成树，以下说法中正确的是（）。 .该图的所有最小生成树的总代价一定是唯一的该图的所有最小生成树的总代价一定是唯一的 .该图的最小生成树是唯一的该图的最小生成树是唯一的 .用用Prim算法从不同顶点开始构造的所有最小生成树一定相同算法从不同顶点开始构造的所有最小生成树一定相同 .使用
4、使用Prim和和Kruskal算法得到的最小生成树总不相同算法得到的最小生成树总不相同 A.仅仅B.仅仅C.仅仅、仅仅、 A 6/18 2最 短 路 径 源点源点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 时间
5、复杂度：时间复杂度：O(n2) 7/18 Dijkstra算法是（算法是（ ）方法求出图中从源点到其余顶点最短路径的。）方法求出图中从源点到其余顶点最短路径的。 A.按长度递减的顺序求出图的某顶点到其余顶点的最短路径按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B.按长度递增的顺序求出图的某顶点到其余顶点的最短路径按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C.通过深度优先遍历求出图中某顶点到其余顶点的最短路径通过深度优先遍历求出图中某顶点到其余顶点的最短路径 D.通过广度优先遍历求出图中某顶点到其余顶点的最短路径通过广度优先遍历求出图中某顶点到其余顶点的最短路径 S 加入加入S
6、集合的顶点：集合的顶点： 最短路径不再改变 越后加入的顶点，dist越长 8/18 以下叙述正确的是（以下叙述正确的是（ ）。）。 A. 最短路径一定是简单路径最短路径一定是简单路径 B. Dijkstra算法不适合有回路的带权图求最短路径算法不适合有回路的带权图求最短路径 C. Dijkstra算法不适合求任意两个顶点的最短路径算法不适合求任意两个顶点的最短路径 D. Floyd算法求两个顶点的最短路径时，算法求两个顶点的最短路径时，pathk-1一定是一定是pathk的子集的子集 9/18 ij 0n-1 迭代迭代时间复杂度：时间复杂度：O(n3) 10/18 Dijkstra算法用于求单
7、源最短路径，为了求一个图中算法用于求单源最短路径，为了求一个图中所所 有顶点对有顶点对之间的最短路径，可以以每个顶点作为起点调用之间的最短路径，可以以每个顶点作为起点调用 Dijkstra算法，算法，Floyd算法和这种算法相比，有什么优势？算法和这种算法相比，有什么优势？ 从每个顶点调用从每个顶点调用Dijkstra算法算法 Floyd算法算法 时间复杂度：时间复杂度：O(n3) 从每个顶点调用从每个顶点调用Dijkstra算法：独立算法：独立 Floyd算法：算法：A共享共享 Floyd算法性能更好 11/18 设下图中的顶点表示村庄，有向边代表交通设下图中的顶点表示村庄，有向边代表交通
8、路线，若要建立一家医院，试问建在路线，若要建立一家医院，试问建在哪一个村庄哪一个村庄 能使各村庄总体交通代价最小。能使各村庄总体交通代价最小。 03 3 12 1212 1313 4 4 5 3 15 6 12/18 利用利用Floyd算法任意两个顶点之间的最短路径长度算法任意两个顶点之间的最短路径长度 036207 22012174 341202916 5811012 18416130 4A 求得每对村庄之间的最少交通代价求得每对村庄之间的最少交通代价 医院建在的村庄医院建在的村庄各村庄往返总的交通代价各村庄往返总的交通代价 012+16+4+7+13+16+4+18=90 113+29+1
9、7+20+12+8+5=115 216+11+12+6+16+29+12+34=136 34+8+12+3+4+17+12+22=82 418+5+34+22+7+20+6+3+0=115 把医院建在村庄3时总体交通代价最少。 13/18 3拓 扑 排 序 找入度为找入度为0的顶点的顶点 输出该顶点，删除从输出该顶点，删除从 它出发的所有出边它出发的所有出边 成功：产生所有顶点的拓扑序列：产生所有顶点的拓扑序列 不成功：不能产生所有顶点的拓扑序列：不能产生所有顶点的拓扑序列 14/18 若一个有向图中的顶点不能排成一个拓扑序列，若一个有向图中的顶点不能排成一个拓扑序列， 则可断定该有向图（则可
10、断定该有向图（ ） A.是个有根有向图是个有根有向图 B.是个强连通图是个强连通图 C.含有多个入度为含有多个入度为0的顶点的顶点 D.含有顶点数目大于含有顶点数目大于1的强连通分量的强连通分量 不能排成一个拓扑序列不能排成一个拓扑序列有回路有回路顶点数大于顶点数大于1的强连通分量的强连通分量 15/18 若用邻接矩阵存储有向图，矩阵中主对角线以下的元若用邻接矩阵存储有向图，矩阵中主对角线以下的元 素均为零，则关于该图拓扑序列的结论是（素均为零，则关于该图拓扑序列的结论是（ ）。）。 A.存在，且唯一存在，且唯一B.存在、且不唯一存在、且不唯一 C.存在，可能不唯一存在，可能不唯一D.无法确定
11、是否存在无法确定是否存在 有向图：顶点有向图：顶点i j（ij）可能有边，而顶点）可能有边，而顶点j i一定没有边一定没有边 该有向图中一定没有回路该有向图中一定没有回路 可以产生拓扑序列，但拓扑序列不一定唯一可以产生拓扑序列，但拓扑序列不一定唯一 16/18 4关 键 路 径 对事件（顶点）进行拓扑排序对事件（顶点）进行拓扑排序 按按拓扑序列拓扑序列求所有事件的最早开始时间求所有事件的最早开始时间 按按拓扑逆序列拓扑逆序列求所有事件的最迟开始时间求所有事件的最迟开始时间 求所有活动（边）的最早开始时间求所有活动（边）的最早开始时间 求所有活动的最迟开始时间求所有活动的最迟开始时间 关键活动：最早开始时间关键活动：最早开始时间=最迟开始时间最迟开始时间 17/18 以下对于以下对于AOE网的叙述中，网的叙述中，错误错误的是（的是（ ）。）。 A.在在AOE网中可能存在多条关键路径网中可能存在多条关键路径 B.关键活动不按期完成就会影响整个工程的完成时间关键活动不按期完成就会影响整个工程的完成时间 C.任何一个关键活动提前完成，整个工程也将提前完成任何一个关键活动提前完成，整个工程也将提前完成 D.所有关键活动都提前完成，整个工程也将提前完成所有关键活动都提前完成，整个工程也将提前完成 18/18