我要讲的图论3课件.pptVIP

A B C D E F 10 10 15 12 12 8 7 6 6 5 一、Prim算法例子求解－3 解： 入选集U 未入选集V 符合条件的边 A,B,D {C,E,F} (A,C)/12；(A,E)/15 ；(B,C)/7 (B,F)/6；(D,F)/6； ,F 第3条边： (F,C)/8； (F,E)/10； A B C D E F 10 10 15 12 12 8 7 6 6 5 一、Prim算法例子求解－4 解： 入选集U 未入选集V 符合条件的边 A,B,D,F {C,E} (A,C)/12；(A,E)/15 ；(B,C)/7 (F,C)/8； (F,E)/10； 第4条边： ,C (C,E)/12 A B C D E F 10 10 15 12 12 8 7 6 6 5 一、Prim算法例子求解－5 解： 入选集U 未入选集V 符合条件的边 A,B,D,F,C {E} (A,E)/15；(F,E)/10；(C,E)/12 第5条边： ,E 一、Prim算法例子求解－6 解： 5 A B C D E F 10 7 10 A B C D E F 10 10 15 12 12 8 7 6 6 5 6 注：最小生成树不唯一，但权值之和相同。 （二）Kruskal算法(Kruskal,1956) 基本思想： 每次选择符合下列条件的边：和已选边不构成回路的权值最小的边。 二、Kruskal算法－1 要在 n 个小区间建立能源网，现在要考虑的问题如何在保证 n 个小区连通的前提下最节省经费? A B D F C E 10 5 12 15 12 10 7 6 6 10 例 二、Kruskal算法－2 根据Kruskal算法的基本思想，每次都选择和已选边不构成回路的权值最小的边。 A B D F C E 10 5 12 15 12 10 7 6 6 10 A B D F C E 10 5 7 6 10 思考题 判断回路的方法：电位法 A B D F C E 10 5 12 15 12 10 7 6 6 10 A B D F C E 10 5 7 6 10 1 2 4 3 5 6 1 4 2 2 6 2 3 5 2 1 1 1 1 1 （三）破圈法 由Rosentiehl于1967年和管梅谷于1975年分别提出； 基本思想： 每次去掉图中圈的最大边，直到图中无圈。 三、破圈法－1 要在 n 个小区间建立能源网，现在要考虑的问题如何在保证 n 个小区连通的前提下最节省经费? A B D F C E 10 5 12 15 12 10 7 6 6 10 例 根据破圈法的基本思想，每次去掉图中圈的最大边，直到图中无圈。 A B D F C E 10 5 12 15 12 10 7 6 6 10 A B D F C E 10 5 7 6 10 12 12 15 10 64 68 68 65 50 50 61 45 60 54 例9：如下图G，求最小生成树： 最小生成树 A B ①　6 　②　　　　　　　　 　 ① 6 6 3 2 　　　　　 　　11 ③ 7 ④　2　 　⑤ 　　 　4 　 ② 16 8 3 4 3 15 18 ⑥ 　1　 ⑦　　　　 　 ③　　　2　 　 　④　 ㈡ 求下列二图的最小生成树 求最小生成树 2 1 4 5 6 3 1 3 2 8 6 4 2 2 * 步骤： 1、 选入A，此时S=A 最短路径A A=0. 以A为中间点，从A开始找 （S集合中） （U集合中） U=B、C、D、E、T A B=6 A D、E、F=无穷大 A C=3 发现 的权植最短。 A C=3 2、 （S集合中） 选入C，此时S=A、C 以C为中间点，从 这条最短路开始找 A C=3 最短路径A A=0, A C=3. （U集合中） U=B、D、E、T 发现 的权植最短。 A C B=5 A C D=6 A C E=7 A C F=无穷大 （比上面第一步