避圈法求最小生成樹

當今社會很多人都不熟悉避圈法及的算法特別是用避圈法生成小樹的基本算法，以及相關的知識，那麼現在就跟隨小編來熟悉瞭解一下吧。

　　什麼是避圈法

簡單説 就是你現在圖上隨便找一個點 然後看與這個點相連的線 找其中最短的一條 確定下來 此時你有兩個點(初始點和你確定下來的線所連接的點)在這兩個點發散出去的線裏找一條最短的 確定子下來 這樣你就有兩條線三個點了 以此類推當包含所有點事 所確定的就是最小支撐樹 但是確定線還有一個原則就是如果你一進確定下來好幾個點好幾條線 那是如果下一條將要確定的最短線正好會使你確定的線形成圈(環形)那麼這條線即使是最短的線也不能取 要換一條線確定。

　　最小生成樹案例

案例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]ost=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的算法。

另外有兩種方法，一種是破圈法，另一種是避圈法。

破圈法是“見圈破圈”，即如果看到圖中有一個圈，就將這個圈的邊去掉一條，直至圖中再無一圈為止。(其中破圈法的" 圈"指的是迴路)

避圈法則採取先將圖中的點都取出來，然後，逐漸向上面添邊，並保證後添入的邊不與以前添上的邊構成圈就可以了，這個過程直到將邊集中能加入的邊(加入後不夠成圈)都加完為止。