首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
admin
2019-01-16
106
问题
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
选项
答案
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
学硕统考专业
相关试题推荐
17世纪英国资产阶级革命中,曾利用了古老文件同专制王权作斗争。这一古老文件是()
阅读以下史料,并回答问题:“古之有国家迫于危亡者,不过守与奔而已。今以守无人,以奔则无地,所以諰諰然惟冀阁下之见哀而赦已,前者连奉书,愿削去旧号,是天地之间,皆大金之国,而尊无二上,亦何劳师远涉而后为快哉!”(宋高宗致信金兵元帅)
简述中央官制从秦汉的三公九卿制到隋唐的三省六部制的演变过程。
反映近代资产阶级政治思想萌芽的著名代表人物是()。
第一次国共合作采取了共产党员以个人身份加入国民党的“党内合作”方式,最早提出这种方式的是()。
在西欧列强海外殖民扩张进程中,各国之间相互争夺海上霸权。18世纪末,英国在争霸中取得胜利的根本原因在于()
以下()协议完成了从网卡到IP地址的映射。
一个客户机利用FTP协议从服务器上下载文件,如下图所示为整个过程中协议交换的过程,请回答如下问题:(1)该协议层图中第四层协议是什么?(2)如果FTP客户端采用了LIST命令来获得FTP服务器上的文件列表,该列表采用什么端口传输?
设某系统有两种磁盘配置:一种单磁盘结构,一种4磁盘组阵列结构。每个磁盘每磁道64个扇区,每扇区1024.字节,转速为10000rpm。找道时间为6ms。两种结构的磁盘控制器每次访问的延迟时间均为1ms。设I/O系统的性能只与磁盘和控制器有关,单磁
某网络拓扑如图A-3所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口LO连接路由器R2,并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1,R2的L0接口的IP地址是202.118.2.2,L1接
随机试题
1999年10月,郭某被法院以盗窃罪判处有期徒刑3年,以侵占罪判处有期徒刑4年,合并执行有期徒刑6年。郭某服刑后不断申诉。2005年4月,法院经审判监督程序对该案再审。再审判决维持了原审法院对郭某盗窃罪的判决部分,撤销了对郭某侵占罪的判决部分,随即释放。郭
用A*=lg(B1*)作为危险源分级标准,那么2.5≤A*3.5<5表示()级重大危险源。
SDH设备和波分复用设备相同的测试项目是()。
商场、市场及其内设部门组织开展防火检查培训内容,室外市场不得在高压线下两侧()m以内摆摊设点。
签订对外经济贸易合同时控制汇率风险的首要步骤是()。
春秋战国时期学术思想比较自由,史称百家争鸣。以下对应正确的有()。
按《国际海事委员会海运单统一规则》规定:“如信用证无特殊规定,银行将拒收在运输单据签发日期后超过21天才提交的单据。在任何情况下,交单不得晚于信用证到期日”。()
目前,中国互联网的最大变局莫过于PC互联网向移动互联网的转变。通俗些说,即在台式机、笔记本等个人电脑上上网的方式将被移动设备上上网的方式取代。这个变化背后则意味着互联网商业模式的革命。举最简单的例子,在互联网广告的“1.0时代”,门户网站广告很大部分来自于
若有定义语句:char*s1="OK",*s2="ok";以下选项中,能够输出"OK"的语句是
互联网不仅给人们的生活带来了便利,也带来了很多隐患,尤其是个人信息的泄漏。上海的一项网上调查显示:97.4%的受访者称曾收过垃圾短信(spammessage)或骚扰电话(harassmentcall),60%受访者认为个人信息安全存在风险。个人信息泄露
最新回复
(
0
)