破圈法求最小支撐樹？1. 作為一個例子，如何使用斷圓法找到最小生成樹？2. 首先，你需要看下圖所示的圓，去掉重量最大的“6”邊。3. 然后看它旁邊的圓圈，繼續(xù)刪除最強(qiáng)大的“7”邊。4. 那么我們應(yīng)該繼

破圈法求最小支撐樹？

1. 作為一個例子，如何使用斷圓法找到最小生成樹？

2. 首先，你需要看下圖所示的圓，去掉重量最大的“6”邊。

3. 然后看它旁邊的圓圈，繼續(xù)刪除最強(qiáng)大的“7”邊。

4. 那么我們應(yīng)該繼續(xù)擴(kuò)大范圍。在這個大圓圈里，我們應(yīng)該去掉最有力的“5”面。

5. 當(dāng)雙方擁有相同的權(quán)利時，您可以隨意刪除“4”面。

6. 最后，我們可以得到如下結(jié)果，如圖所示

循環(huán)避免方法：首先，根據(jù)權(quán)重從小到大排列邊緣：（a，b）（a，c）（b，c）（b，d）（b，e）（c，e）（a，e）（d，e）（a，d），然后?。╝，b）（a，c），棄（b，c），?。╞，d）（b，e），棄（c，e）（a，e）（a，d），計算完畢。得到的最小生成樹如下圖所示，w（T）=28[避免圓法，即選擇時避免取出一個圓

避免圓的方法是：只要不形成環(huán)，就始終找到最短邊，然后保留它。斷圓的方法是：當(dāng)你看到循環(huán)時，先找到循環(huán)的最長邊，然后將其消除，再找到下一個循環(huán)的最長邊進(jìn)行消除

prim（prim）算法設(shè)為n=（V，e，c）連通網(wǎng)絡(luò)，Te是n的最小生成樹的邊集。

①算法開始時，u={u o}（u o∈V），Te=0；

②找到滿足權(quán)（u，V）=min{weight（u 1，V 1）| u 1∈u，V 1∈V-u}的邊，并將其合并到集Te中，同時將V合并到u中。

③反復(fù)執(zhí)行算法，直到v=U