Prim算法求解过程.pdf

Prim 算法求解过程 一、算法用途 ：从某给定点开始 ，求解无向连通加权图G=(V, E, W)的最小生成树 T=(VT, ET, WT). 二、算法步骤 ： 设 G=(V, E, W)是无相连通加权图， |V|=n, |E|=m。 （要求从 v1 点开始求解 ） Step 1 . 令已经落在树中的点集VT=v1, ET=, 尚未落在树 T 上的点集 VT=V-VT； Step 2. 找集合 VT与VT之间的权最小的边e=(vi,vj)，其中 viVT, vjVT； 令 VT:=VTv j, VT:= VT -vj, ET:=ETe ； Step 3. 当 VT=V, VT= 时，算法中止，即得到原图G 的一棵最小生成树，再计算 WT. 三、例题 求图 1 的最小生成树。 （从 v1 点开始 ） 解 解法过程一：图示法。 v1 VT=v 1, VT=V-VT=v2, v3, , v6. VT=v 1,v2, VT=v 3, , v6. 7 5 1 2 v1 v3 v5 v6 4 1 2 3 6 图 1 v2 v4 v1 v2 1 VT=v1,v2,v3, VT=v4,v5,v6 VT=v1,v2,v3, v5, VT=v4,v6 VT=v1,v2,v3, v5, v4, VT=v6 6 VT=v1,v2,v3, v5, v4, v6=V, VT=，算法中止。 所以， T 如上图所示且 WT=9. v3 v1 v5 v1 v5 v3 v2 v5v3 v4 v6 v2 v1 2 1 1 1 1 1 2 3 v2 2 1 v1 v4 v3 v2 1 2 2 2 解法过程二：列表法。 步 骤 VTVT VT与VT 之间的 最短边 最短边的 权 树权 1 v1v2,v3,v4,v5,v6(v1,v2) 1 1 2 v1,v2v3,v4,v5,v6(v2,v3) 2 3 3 v1,v2,v3v4,v5,v6(v3,v5) 1 4 4 v1,v2,v3,v5v4,v6(v5,v4) 3 7 5 v1,v2,v3,v5,v4v6(v4,v6) 2 9 6 v1,v2,v3,v5,v4,v6- - - 最终得到 G 的最小生成树 T 如下图所示， WT=9. （注：做此类题目时请选取上述两种过程中的一种规范书写。） 四、思考题： 1. 此算法的最终结果与起始点的选取有没有关系？ 2. 起始点相同的情况下，最后结果（最小生成树和WT）会不会不同？ （试从 v1开始求图 2 的最小生成树） 3. 算法中每一步加边时是否需要考虑避免与已经在T 中的边回路？为什么？ 4. 此算法每一步都是选取VT与VT两点集之间的边（即e=(vi,vj), viVT, vjVT） 中权最小的边，而不是这一步新加入VT的点的邻边中权最小的，否则得到的不是最 小生成树（例如图 2） 。 v2 v2v2 v2 v2 1 1 2 2 3 1 3 5 4 v5 v3 v6 v1 v4v2 1 1 2 2 3 五、Kruskal 算法与 Prim 算法的区别： 求最小生成树 的算法 起始步骤算法过程适合范围时间复杂度 Kruskal 算法 最小权的边 （求解者自行 选取） 通过每一步选 取最短边来找 到最小生成树 稀疏图 O(mlogm), m 是图 G 的边数 Prim 算法 规定了算法的 起始点 每一步通过选 取点集 VT和 VT之间的最 短边来进一步 更新这两个点 集 稠密图O(n 2) D 氏算法求解过程 例题试求无向赋权图中v1到 v6的最短路径。 解： D氏算法的具体步骤如下表所示： 步 骤 永 久标号点集 P 最近 距离点 最短 距离 D(v2) D(v3) D(v4) D(v5) D(v6) 1 v1v21 1 4 2 v1, v2v33 1* 3 8 6 3 v1, v2, v3v54 1* 3* 8 4 4 v1, v2, v3, v5v47 1* 3* 7 4* 10 5 v1, v2, v3, v5, v4v69 1* 3* 7* 4* 9 6 v1, v2, v3, v5, v4, v6 - - 1* 3* 7* 4* 9* 从而， v6的 P标号为 9，即 v1到 v6的最短距离是9. v2 v4 7 5 1 2 v1 v3 v5 v6 4 1 2 3 6 图 2 注： 1.“最短距离”表示在当前集合T中的最短距离； “最近距离点”为其相应的结点。 2.D(vi)表示各结点当前的标号 3.* 表示新加入集合P中的点。 4.作业、测验题中若有求解最短路径问题时，请画出此表格表明求解过程。 思考题： 1.最终完成此表后，如何找到从v1出发到某点 vi的最短路径？ 2.若在算法过程中某一步出现了两个相等的最短距离值时，选取哪一个加入集合P？ 提示 ：可从以下两类问题考虑： (1) 求从 v1 出发到某点vi 的最短距离； (2) 求从 v1 出发到其它各点的最短距离。 Kruskal算法（避圈法）求解过程 一、算法用途 ：求解无向连通加权图G=(V, E, W) 的最小生成树 T=(VT, ET, WT). 二、算法步骤 ： 设 G=(V, E, W) 是无相连通加权图， |V|=n, |E|=m。不妨设 G中没有环， 否则把所有的环先去掉。 Step 1 . 按照边权从小到大的关系，将m条边排序：e1, e2, ., em; Step 2. 取 e1ET，然后依次检查 e2, e3, , em. 若 ej(j2)与已经在 T 中的边 不构成回路，则取ejET，否则就舍弃 ej； Step 3. 当 VT=V（或|ET|=n-1，或加入任何一条边都产生回路）时，算法中止，即得到原 图 G 的一棵最小生成树，再计算WT。 三、例题 求此无向连通加权图的最小生成树。 解 对图中各边的权进行从小到大排序： e1=(v1,v2), e2=(v3,v4), e3=(v2,v3), e4=(v4,v6), e5=(v4,v5), e6=(v1,v3), e7=(v2,v5), e8=(v5,v6) e9=(v2,v4) 7 5 1 2 v1 v3 v5 v6 4 1 2 3 6 v2 v4 则由 Kruskal 算法，最小生成树的边集合的序列为： 所以， T 如上图所示且 WT=9. （注：做此类题目时请按照上述过程规范书写。） 四、思考题： v1 v2 v2 v3 v1 v5 v1 v2 v5 v3 v4 v1 v3 v5 v6 v5v3 v4 v6 v2 v2 v1 1 2 1 1 2 1 1 1 1 1 1 2 2 2 3 1. 此算法的最终结果与起始边的选取有没有关系？ 2. 能否用此算法得到最小生成子图（连通或不连通，边数介于0 和 n-1 之间）？ 3. 能否用破圈法设计一个求最小生成树的算法吗？