破圈法求最小生成树|避圈法求最小生成树

　　当今社会很多人都不熟悉避圈法及的算法特别是用避圈法生成小树的基本算法，以及相关的知识，那么现在就跟随小编来熟悉了解一下吧。

　　什么是避圈法

　　简单说就是你现在图上随便找一个点然后看与这个点相连的线找其中最短的一条确定下来此时你有两个点(初始点和你确定下来的线所连接的点)在这两个点发散出去的线里找一条最短的确定子下来这样你就有两条线三个点了以此类推当包含所有点事所确定的就是最小支撑树但是确定线还有一个原则就是如果你一进确定下来好几个点好几条线那是如果下一条将要确定的最短线正好会使你确定的线形成圈(环形)那么这条线即使是最短的线也不能取要换一条线确定。

　　最小生成树案例

　　案例1

　　1、对于连通的带权图(连通网)G，其生成树也是带权的。生成树T各边的权值总和称为该树的权。

　　这里:

　　TE表示T的边集

　　w(u，v)表示边(u，v)的权。

　　权最小的生成树称为G的最小生成树(Minimum SpannirngTree)。最小生成树可简记为MST。

　　2、生成树和最小生成树的应用

　　生成树和最小生成树有许多重要的应用。

　　【例】网络G表示n各城市之间的通信线路网线路(其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案。

　　3、最小生成树性质(MST性质)

　　(1)MST性质

　　最小生成树性质：设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中所有的一个端点在U(u∈U)里、另一个端点不在U(即v∈V-U)里的边中，具有最小权值的一条边，则一定存在G的一棵最小生成树包括此边(u，v)。

　　案例2

　　假设 N=(V，E)是一个带权图，TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v) ∈E中找一条权值最小的边(u，v)并入集合TE，同时v并入U，直至U=V为止。此时TE中必有n-1边，则T=(V，{TE})为N的最小生成树。

　　为实现这个算法需附设一个辅助数组 closedge，以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[I-1]，它包括两个域，其中lowcost存储该边上的权：显然， closedge[I-1].Lowcost=Min{cost(u，vi)|uEU} vex域存储该边依附的在U中的顶点。

　　最易短路的三种基本算法

　　1、Kruskal算法，Prim算法，两种算法都是采取的同种贪心策略，其实证明这个贪心策略是一样的结论

　　2、Kruskal算法的时间复杂度，O(ElgE)排序+O( ( E + V)A(V)) E的find_set。V的union = O( ElgE) 然后E

　　3、 Prim算法，用最小二项堆的话，O(V)堆初始化+O(VlgV)取出最小的元素 + O (ElgV ) 维护最小堆 = O( (E+V)lgV )=O(ElgV)

　　过可以用斐波那契堆，那么一次插入是O(lgV ) 每次删除平摊O (1)　，所以总的时间复杂度是　O　(E+VlgV)

　　与避圈法对应的破圈法

　　破圈法，寻找一个连通图的最小支撑树(最小部分树、最小生成树)，也就是BST的一种方法。Kruskal,Prim也是求BST的算法。

　　编辑摘要

　　破圈法：寻找一个连通图的最小支撑树(最小部分树、最小生成树)，也就是BST的一种方法。Kruskal,Prim也是求BST的算法。

　　另外有两种方法，一种是破圈法，另一种是避圈法。

　　破圈法是“见圈破圈”，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。(其中破圈法的" 圈"指的是回路)

　　避圈法则采取先将图中的点都取出来，然后，逐渐向上面添边，并保证后添入的边不与以前添上的边构成圈就可以了，这个过程直到将边集中能加入的边(加入后不够成圈)都加完为止。