资源描述：
《prim算法求解过程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Prim算法求解过程一、算法用途：从某给定点开始，求解无向连通加权图G=(V,E,W)的最小生成树T=(VT,ET,WT).二、算法步骤：设G=(V,E,W)是无相连通加权图，
2、V
3、=n,
4、E
5、=m。（要求从v1点开始求解）Step1.令已经落在树中的点集VT={v1},ET=Φ,尚未落在树T上的点集～VT=V-VT；Step2.找集合VT与～VT之间的权最小的边e=(vi,vj)，其中vi∈VT,vj∈～VT；令VT:=VT∪{vj},～VT:=～VT-{vj},ET:=ET∪{e}；Step3.当VT=V,～VT=
6、Φ时，算法中止，即得到原图G的一棵最小生成树，再计算WT.v2v4三、例题7512v1v3v5v641236图1求图1的最小生成树。（从v1点开始）[解]解法过程一：图示法。①v1VT={v1},～VT=V-VT={v2,v3,…,v6}.v2②1v1VT={v1,v2},～VT={v3,…,v6}.1v2③2v1v3VT={v1,v2,v3},～VT={v4,v5,v6}v12v21④v5v31v4v2VT={v1,v2,v3,v5},～VT={v4,v6}⑤122v11v5v3VT={v1,v2,v3,v5,v4}
7、,～VT={v6}v2v421v132v61v3v5VT={v1,v2,v3,v5,v4,v6}=V,～VT=Φ，算法中止。所以，T如上图所示且WT=9.解法过程二：列表法。步骤VT～VTVT与～VT之间的最短边最短边的权树权1v1v2,v3,v4,v5,v6(v1,v2)112v1,v2v3,v4,v5,v6(v2,v3)233v1,v2,v3v4,v5,v6(v3,v5)144v1,v2,v3,v5v4,v6(v5,v4)375v1,v2,v3,v5,v4v6(v4,v6)296v1,v2,v3,v5,v4,v6Φ
8、----------------最终得到G的最小生成树T如下图所示，WT=9.v4v221v623v11v3v5（注：做此类题目时请选取上述两种过程中的一种规范书写。）四、思考题：1.此算法的最终结果与起始点的选取有没有关系？2.起始点相同的情况下，最后结果（最小生成树和WT）会不会不同？（试从v1开始求图2的最小生成树）3.算法中每一步加边时是否需要考虑避免与已经在T中的边回路？为什么？4.此算法每一步都是选取VT与～VT两点集之间的边（即e=(vi,vj),vi∈VT,vj∈～VT）中权最小的边，而不是这一步新加入
9、VT的点的邻边中权最小的，否则得到的不是最小生成树（例如图2）。v221231v2v2531v24v2图2五、Kruskal算法与Prim算法的区别：求最小生成树的算法起始步骤算法过程适合范围时间复杂度Kruskal算法最小权的边（求解者自行选取）通过每一步选取最短边来找到最小生成树稀疏图O(mlogm),m是图G的边数Prim算法规定了算法的起始点每一步通过选取点集VT和～VT之间的最短边来进一步更新这两个点集稠密图O(n2)D氏算法求解过程[例题]试求无向赋权图中v1到v6的最短路径。v2v47512v1v3v5v
10、641236解：D氏算法的具体步骤如下表所示：步骤永久标号点集P最近距离点最短距离D(v2)D(v3)D(v4)D(v5)D(v6)1v1v2114∞∞∞2v1,v2v331*386∞3v1,v2,v3v541*3*84∞4v1,v2,v3,v5v471*3*74*105v1,v2,v3,v5,v4v691*3*7*4*96v1,v2,v3,v5,v4,v6------------1*3*7*4*9*从而，v6的P标号为9，即v1到v6的最短距离是9.注：1.“最短距离”表示在当前集合T中的最短距离；“最近距离点”为其
11、相应的结点。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).
12、二、算法步骤：设G=(V,E,W)是无相连通加权图，
13、V
14、=n,
15、E
16、=m。不妨设G中没有环，否则把所有的环先去掉。Step1.按照边权从小到大的关系，将m条边排序：e1,e2,...,em;Step2.取e1∈ET，然后依次检查e2,e3,…,em.若ej(j≥2)与已经在T中的边不构成回路，则取ej∈ET，否则就舍弃ej；St
