[理学]数据结构第七章-图.ppt

7.5 两点之间的 最短路径问题 求从某个源点到其余各点的最短路径 k = minimum(closedge); // 求出加入生成树的下一个顶点(k) // 此时closedge[k].lowcost= // MIN{closedge[vi ].lowcost|closedge[vi].lowcost0, Vi∈V-U} printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树上一条边的两个顶点 closedge[k].lowcost = 0; // 第k顶点并入U集 for (j=0; jG.vexnum; ++j) // 修改其它顶点的最小边 if (G.arcs[k][j].adj closedge[j].lowcost) // 新顶点并入U后重新选择最小边 closedge[j] = { G.vexs[k], G.arcs[k][j].adj }; a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b 7 a a a 19 14 18 0 e 12 e e 8 16 0 d 3 d d 7 21 0 c 5 0 g f a b c d e f g a ∞ 19 ∞ ∞ 14 ∞ 18 b 19 ∞ 5 7 12 ∞ ∞ c ∞ 5 ∞ 3 ∞ ∞ ∞ d ∞ 7 3 ∞ 8 21 ∞ e 14 12 ∞ 8 ∞ ∞ 16 f ∞ ∞ ∞ 21 ∞ ∞ 27 g 18 ∞ ∞ ∞ 16 27 ∞ 0 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 （2）克鲁斯卡尔算法的基本思想 a b c d e g f 19 5 14 18 27 16 8 21 3 a e 12 d c b g f 7 14 8 5 3 16 21 例如: 7 12 18 19 a b c d e g f 5 14 16 8 21 3 算法描述: 构造非连通图 ST=( V,{ } ); //v表示顶点的集合， //{ }表示边的集合，首先是空 k = i = 0; // k 计选中的边数 while (kn-1) { ++i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k++; } 普里姆算法 克鲁斯卡尔算法 时间复杂度 O(n2) O(eloge) 稠密图 稀疏图 算法名 适应范围 （3）比较两种算法 每一对顶点之间的最短路径 1、从某个源点到其余各点的最短路径 V5 V0 V1 V2 V3 V4 5 10 10 20 30 50 60 100 始点 终点 最短路径 路径长度 V0 V1 V2 V3 V4 V5 带权有向图中从V0到其余各顶点之间的最短路径： 无 (V0, V2) 10 (V0,V4,V3) 50 (V0,V4) 30 (V0,V4,V3,V5) 60 如何求从源点到其余各点的最短路径？ 算法的基本思想: 按路径长度递增的次序产生最短路径 源点 v1 vn V3 … 其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。 v2 下一条最短路