用破圈法求最小生成树
求最小生成树的破圈法的源程序代码以及流程图(不要Prim和Kruskal算法的）
望编程高手赐教```紧急````
破圈算法是1975年由我国数学家管梅谷教授提出来的.
基本思想：在给定的图中任意找出一个回路,删去该回路中权最大的边.然后在余下的图中再任意找出一个回路,再删去这个新找出的回路中权最大的边,……一直重复上述过程,直到剩余的图中没有回路.这个没有回路的剩余图便是最小生成树.
算法的基本思想
先将图G 的边按权的递减顺序排列后, 依次检
验每条边, 在保持连通的情况下, 每次删除最大权
边, 直到余下n- 1 条边为止.
2.3 算法的理论基础
定理1: 任意图G 有支撑树的充分必要条件是
图G 是连通的.
定理2: 图G= ( V, E) 是一个树的充分必要
条件是G 是连通图, 且e=n- 1 [5].
2.4 算法的实现
先将图G 的边按权的递减顺序排列, 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) 权尽可能
大; 第3 步: 若i