首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
admin
2019-01-16
67
问题
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
选项
答案
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
学硕统考专业
相关试题推荐
19世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
下列不属于苏联战时共产主义政策内容的是()。
阅读材料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为仁,以神
阅读以下史料,并回答问题:“古之有国家迫于危亡者,不过守与奔而已。今以守无人,以奔则无地,所以諰諰然惟冀阁下之见哀而赦已,前者连奉书,愿削去旧号,是天地之间,皆大金之国,而尊无二上,亦何劳师远涉而后为快哉!”(宋高宗致信金兵元帅)
春秋战国时期,提出“祸兮福之所倚,福兮祸之所伏”的思想家是()。
第二次世界大战后,世界形势变化的最大特点是()。
古巴革命党是由古巴民族英雄、民族解放运动的领袖()于1892年在美国纽约建立的。
在意大利统一过程中,加富尔为了获得拿破仑三世的支持,让与法国的领土是()。
明末清初,著名学者()抗清失败,前往日本讲学,传播中国文化。
Demandpaging算法是paging算法在虚拟存储空间管理的扩展。其主要的改进是:仅当需要访问某页面时,如果它不在内存,把它调入内存。按照这个思路,将segmentation算法(段式存储管理算法)扩展到虚拟存储空间管理,也可以产生类似的算法,不妨
随机试题
有关研究表明,道德发展的最低层次是()
下列关于乳酸脱氢酶的叙述,错误的是
定影液的组成不包括
根据我国《城市房屋拆迁管理条例》的规定,拆迁人应当自拆迁委托合同订立之日起()日内,报房屋拆迁管理部门备案。
下列关于员工对工作不满的反应的陈述不正确的是()。[2007年真题]
教育过翟中的师生关系是知识授受的关系。()
新课程认为老师既是课程的执行者,也是课程的建设者,所以,语文教师要努力建设开放而__________的语文课程。
下列()造成学生伤害事故,学校已经履行了相应的职责,行为并无不当,无法律责任。
今发现的宋庆龄写给宋子文的私信以及孔令仪的回忆都证明当年国民政府交通部部长张嘉趁的更正函所述是事实,即飞机所运为美国飞行员的“洋狗”。然而,可惜的是,当时大部分人都不予采信。多年来,几乎所有相关的历史著作都在继续宣扬:香港危急之时,孔家抢运“洋狗”。以讹传
WhatisthereasonforcallingtheU.S.a"meltingpot"?
最新回复
(
0
)