首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
admin
2019-01-16
28
问题
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
选项
答案
void SpnTree(AdjList g){ //用“破圈法”求解带权连通无向图的一棵最小代价生成树 typedef struct{int i,j,w;}node; //设顶点信息就是顶点编号,权是整数 node edge[]; scanf(”%d%d”,&e,&n); //输入边数和顶点数 for(i=1;i<--e;i++) //输入e条边:顶点,权值 scanf(”%d%d%d”,&edge[i].i,&edge[i].j,&edge[i].w); for(i=2;i<=e;i++){ //按边上的权值大小,对边进行逆序排序 edge[0]=edge[i];J=i-1; while(edge[j].w
=n){ //破圈,直到边数e=n一1 if(connect(k)) //删除第k条边若仍连通 {edge[k].w=0 i eg-一一;} //测试下一条边edge[k],权值置0表示该边被删除 k++;//下条边 }//while } connect()是测试图是否连通的函数,可用DFS函数或BFS函数实现,若是连通图,一次进入DFS函数或BFS函数就可遍历完全部顶点,否则,因为删除该边而使原连通图成为两个连通分量时,该边不应删除。“破圈”结束后,可输出edge中w不为0的n-1条边。
解析
转载请注明原文地址:https://kaotiyun.com/show/ceRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
巴黎和会召开的时间是()。
1979年11月,中共中央委托()主持起草《关于建国以来党的若干历史问题的决议》。
阅读材料,回答以下问题:一、大清帝国之皇统,万世不易。二、皇帝神圣,不可侵犯。三、皇帝权以宪法规定为限。四、皇帝继承之顺序,于宪法规定之。五、宪法由资政院起草议决,皇帝颁布之。六、宪政改正提案权,属于国会。七、上院议员,由国民于法定特别资格公选之。八、总
试述法国大革命的特点及影响。
《中国人民解放军宣言》发表的具体时间是()。
电子计算机的发展经过了:①电子数值积分计算机(ENIAC)②集成电路计算机③大规模集成电路汁算机④晶体管计算机⑤人工智能计算机其先后顺序是()。
已知某32位二进制机器数为11000000000000000000000000000000,试计算在下列各种编码方式下其代表的真值。(1)原码定点小数;(2)补码定点小数;(3)反码定点小数;(4)IEEE754标准短
著名的网络OSI七层模型是由()组织提出来的。
某汽车轮渡口,过江渡船每次能载10辆车过江。过江车辆分为客车类和汽车类,上渡船有如下规定:同类车先到先上船,客车先于货车上船,且每上4辆客车,才允许上一辆货车,若等待客不足4辆,则以货车代替,若无货车等待允许客车都上船。写一算法模拟渡口管理。
随机试题
治疗结核性腹膜炎,最重要的是
再生障碍性贫血的诊断,下列哪一项不正确
休克病人,出现呼吸困难,紫绀,给氧后无改善,PaO2,持续降低至6.8kPa(51mmHg),采取措施正确的是:
阻碍公路建设或抢修,致使公路建设或抢修不能正常进行,尚未造成严重损失的,给予()。
下列经营项目在2002年采用5%税率征收营业税的有( )
《国家突发公共事件总体应急预案》将“防患于未然”作为一个基本要求,“防患于未然”包含的哲理有()。
判断一种所有制经济是否优越的标准是看其
设f(x)二阶可导,f(0)=0,且f’’(x)>0.证明:对任意的a>0,b>0,有f(a+b)>f(a)+f(b).
设有学生选课表SC(学号,课程号,成绩),用SQL命令检索同时选修了课程号为"C1"和"C5"课程的学生的学号的正确命令是( )。
Forthispart,youarerequiredtowriteacompositionbasedonthefollowingoutlinegiveninChinese.Thesuggestedtitleis:
最新回复
(
0
)