用破圈法求最小生成树求最小生成树的破圈法的源程序代码以及流程图(不要Prim和Kruskal算法的）望编程高手赐教```紧急````破圈算法是1975年由我国数学家管梅谷教授提出来的. 基本思想：在给定的图中任意找出一个回路,删去该回路中权最大的边.然后在余下的图中再任意找出一个回路,再删去这个新找出的回路中权最大的边,……一直重复上述过程,直到剩余的图中没有回路.这个没有回路的剩余图便是最小生成树. 算法的基本思想先将图G 的边按权的递减顺序排列后, 依次检验每条边, 在保持连通的情况下,
2019-04-13
用破圈法求最小生成树
求最小生成树的破圈法的源程序代码以及流程图(不要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
优质解答
楼主是文化人啊,我看了半天一个字都没看懂,呵呵把分给我吧,我都没分了,反正你关也是关,
至于问题,你应该问问你同事或者跟你一样水平的朋友.
楼主是文化人啊,我看了半天一个字都没看懂,呵呵把分给我吧,我都没分了,反正你关也是关,
至于问题,你应该问问你同事或者跟你一样水平的朋友.