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

破圈法求最小支撐樹(shù)？

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

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

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

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

5. 當(dāng)雙方擁有相同的權(quán)利時(shí)，您可以隨意刪除“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），計(jì)算完畢。得到的最小生成樹(shù)如下圖所示，w（T）=28[避免圓法，即選擇時(shí)避免取出一個(gè)圓

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

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

①算法開(kāi)始時(shí)，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中，同時(shí)將V合并到u中。

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