用破圈法求最小生成樹
求最小生成樹的破圈法的源程序代碼以及流程圖(不要Prim和Kruskal算法的）
望編程高手賜教```緊急````
破圈算法是1975年由我國數(shù)學(xué)家管梅谷教授提出來的.
基本思想：在給定的圖中任意找出一個(gè)回路,刪去該回路中權(quán)最大的邊.然后在余下的圖中再任意找出一個(gè)回路,再刪去這個(gè)新找出的回路中權(quán)最大的邊,……一直重復(fù)上述過程,直到剩余的圖中沒有回路.這個(gè)沒有回路的剩余圖便是最小生成樹.
算法的基本思想
先將圖G 的邊按權(quán)的遞減順序排列后, 依次檢
驗(yàn)每條邊, 在保持連通的情況下, 每次刪除最大權(quán)
邊, 直到余下n- 1 條邊為止.
2.3 算法的理論基礎(chǔ)
定理1: 任意圖G 有支撐樹的充分必要條件是
圖G 是連通的.
定理2: 圖G= ( V, E) 是一個(gè)樹的充分必要
條件是G 是連通圖, 且e=n- 1 [5].
2.4 算法的實(shí)現(xiàn)
先將圖G 的邊按權(quán)的遞減順序排列, Ei 為刪除
邊集.具體步驟為第1 步: 令i=1, E0=Φ, G0=G;
第2 步: 取邊ei∈E ( Gi- 1) 即E\Ei- 1, 令Ei=Ei- 1∪{ei}, 使得Gi= G [E\Ei] 連通, 且W ( ei) 權(quán)盡可能
大; 第3 步: 若i