当前位置 :
用破圈法求最小生成树求最小生成树的破圈法的源程序代码以及流程图(不要Prim和Kruskal算法的)望编程高手赐教```紧急````破圈算法是1975年由我国数学家管梅谷教授提出来的.基本思想:在
 更新时间:2024-04-25 13:16:21
1人问答
问题描述:

用破圈法求最小生成树

求最小生成树的破圈法的源程序代码以及流程图(不要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)即EEi-1,令Ei=Ei-1∪{ei},使得Gi=G[EEi]连通,且W(ei)权尽可能

大;第3步:若i

卢汉回答:
  楼主是文化人啊,我看了半天一个字都没看懂,呵呵把分给我吧,我都没分了,反正你关也是关,   至于问题,你应该问问你同事或者跟你一样水平的朋友.
数学推荐
最新更新
优秀数学推荐
热门数学
查询网(393r.com)汇总了汉语字典,新华字典,成语字典,组词,词语,在线查字典,中文字典,英汉字典,在线字典,康熙字典等等,是学生查询学习资料的好帮手,是老师教学的好助手。
声明:本网站尊重并保护知识产权,根据《信息网络传播权保护条例》,如果我们转载的作品侵犯了您的权利,请在一个月内通知我们,我们会及时删除。

邮箱:  联系方式:

Copyright©2009-2021 查询网 393r.com 版权所有 闽ICP备2021002823号-6