最小生成树.docx

《最小生成树.docx》由会员分享，可在线阅读，更多相关《最小生成树.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最小生成树2、普里姆Prim算法1算法的基本思想：普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。从连通网络N=V,E中的某一顶点u0出发，选择与它关联的具有最小权值的边(u0,v)，将其顶点参加到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把该边参加到生成树的边集TE中，把它的顶点参加到集合U中。如此重复执行，直到网络中的所有顶点都参加到生成树顶点集合U中为止。假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE

2、是T的边集，则构造G的最小生成树T的步骤如下：1初始状态，TE为空，U=v0，v0V；2在所有uU，vV-U的边(u，v)E中找一条代价最小的边(u，v)并入TE，同时将v并入U；重复执行步骤2n-1次，直到U=V为止。在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。对于每一个顶点vV-U，closestv为U中距离v近期的一个邻接点，即边(v，closestv)是在所有与顶点v相邻、且其另一顶点jU的边中具有最小权值的边，其最小权值为lowcostv，即lowcostv=costvclos

3、estv，采用邻接表作为存储构造：设置一个辅助数组closedge：lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；adjvex域记录生成树顶点集合外各顶点距离集合内哪个顶点近期(即权值最小)。应用Prim算法构造最小生成树的经过:如下所示为构造生成树的经过中，辅助数组中各分量值的变化情况，初始归Uv1，参加到U集合中的节点，我们将lowcost改成0以示：Prim算法1.概览普里姆算法Prim算法，图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点英语：Vertex(graphtheory)，

4、且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫亚尔尼克英语：VojtchJarnk发现；并在1957年由美国计算机科学家罗伯特普里姆英语：RobertC.Prim独立发现；1959年，艾兹格迪科斯彻再次发现了该算法。因而，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆亚尔尼克算法。2.算法简单描绘1).输入：一个加权连通图，其中顶点集合为V，边集合为E；2).初始化：Vnew=x，其中x为集合V中的任一节点起始点，Enew=,为空；3).重复下列操作，直到Vnew=V：a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，

5、并且vV假如存在有多条知足前述条件即具有一样权值的边，则可任意选取其中之一；b.将v参加集合Vnew中，将边参加集合Enew中；4).输出：使用集合Vnew和Enew来描绘所得到的最小生成树。下面对算法的图例描绘图例讲明不可选可选已选Vnew此为原始的加权连通图。每条边一侧的数字代表其权值。-顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D近期的顶点，因而将A及对应边AD以高亮表示。C,GA,B,E,FD下一个顶点为距离D或A近期的顶点。B距D为9，距A为7，E为15，F为6。因而，F距D或A近期，因而将顶点F与相应边DF以高亮表示。C,GB,E,FA,D算法继续重复上

6、面的步骤。距离A为7的顶点B被高亮表示。CB,E,GA,D,F在当前情况下，能够在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E近期，因此将顶点E与相应边BE高亮表示。无C,E,GA,D,F,B这里，可供选择的顶点只要C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。无C,GA,D,F,B,E顶点G是唯一剩下的顶点，它距F为11，距E为9，E近期，故高亮表示G及相应边EG。无GA,D,F,B,E,C克鲁斯卡尔Kruskal算法求最小生成树1、基本思想：设无向连通网为G(V,E)，令G的最小生成树为T(U,TE)，其初态为UV，TE，然后，根据边的权值由小到大的顺

7、序，考察G的边集E中的各条边。若被考察的边的两个顶点属于T的两个不同的连通分量，则将此边作为最小生成树的边参加到T中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T中的连通分量个数为1时，此连通分量便为G的一棵最小生成树。2、示例：1).记Graph中有v个顶点，e个边2).新建图Graphnew，Graphnew中拥有原图中一样的e个顶点，但没有边3).将原图Graph中所有e个边按权值从小到大排序4).循环：从权值最小的边开场遍历每条边直至图Graph中所有的节点都在同一个连通分量中if这条边连接的两个节点于图Grap

8、hnew中不在同一个连通分量中添加这条边到图Graphnew中图例描绘：首先第一步，我们有一张图Graph，有若干点和边将所有的边的长度排序，用排序的结果作为我们选择边的根据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了右图在剩下的变中寻找。我们找到了CE。这里边的权重也是5依次类推我们找到了6,7,7，即DF，AB，BE。下面继续选择，BC或者EF尽管如今长度为8的边是最小的未选择的边。但是如今他们已经连通了对于BC能够通过CE,EB来连接，类似的EF能够通过EB,BA,AD,DF来接连。所以不需要选择他们。类似的BD也已经连通了这里上图的连通线用红色表示了。最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是右：