首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
admin
2019-08-01
24
问题
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
选项
答案
void SpnTree(AdjList g){ //用“破圈法”求解带权连通无向图的一棵最小代价生成树 tvpedef 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<edge[0].w)edge[j+1]=edge[j--]; edge[j+1]=edge[0]; }//for k=1:eg=e; while(eg>=n){ //破圈,直到边数e=n一1 if(connect(k)) //删除第k条边若仍连通 {edge[k].W=0;eg一一;} //测试下一条边edge[k],权值置0表示该边被删除 k++; //下条边 }//while } connect()是测试图是否连通的函数,可用DFS函数或BFS函数实现,若是连通图,一次进入DFS函数或BFS函数就可遍历完全部顶点,否则,因为删除该边而使原连通图成为两个连通分量时,该边不应删除。“破圈”结束后,可输出edge中ω不为0的n—1条边。
解析
转载请注明原文地址:https://kaotiyun.com/show/4NCi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
试述五四运动的意义。
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
乾隆时期,明确规定了驻藏大臣的地位与达赖班禅同等,并实行“金瓶掣签”制度的文件是()。
中国共产党主张和平解决西安事变的主要目的是()。
第二次世界大战后,资本主义经济出现的新特点有()。①美国资本加强了对西欧和日本的渗透②国家开始参与资本主义生产过程③国家成为资本主义私有制的保护者④科技成果更为迅速地转化为生产力
为了加强与乌孙的关系,西汉先后将()和()两位公主远嫁乌孙王,巩固了汉与乌孙的关系。
已知一组关键字为(26,36,41,38,44,15,68,12,6,51,25),用链地址法解决冲突。假设装填因子a=0.75,散列函数的形式为H(K)=KMODP,回答下列问题:(1)构造散列函数。(2)画出散列表。(
下列各部件中不属于控制器的部件是()。
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
设有一个双向链表h,每个结点中除有prior,data和next三个域外,还有一个访问频度域freq,在链表被起用之前,每个结点中的freq域都被初始化为零。每当进行LocateNode(h,x)运算时,令元素值为x的结点中freq域中的值加一,并调整表中
随机试题
“科技刨新2030”是按照《国家创新驱动发展战略纲要》的要求,部署了一批体现国家战略意图的重大项目,力争到2030年在航空发动机及燃气轮机、量子通信与量子计算、脑科学与类脑研究、新一代人工智能等16个重点方向实现率先突破。该材料表明()
慢性肺心病常见的平衡失调是
留取24h尿标本应告知病人从几点开始到几点结束
A注册会计师负责对甲公司2011年度财务报表进行审计。在确定总体应对措施和进一步审计程序的性质、时间安排、范围时,A注册会计师遇到下列事项,请代为作出正确的专业判断。在设计进一步审计程序时,A注册会计师的以下考虑中,正确的有()。
新陈代谢是指地区上的一切生命有机体都需要不断地与周围环境进行()交换。
人口因素在社会发展中的作用是可以()。
在关系模型中,关系的“元数”(arlty)是指(21)。有关系只和S,R ∩ S的运算等价于(22)。设关系R和S的属性个数分别为r和5,则(R×S)操作结果的属性个数为(23)。
InEnglandnofemaleswereallowedtovoteinnationalelectionsbefore______.
AlthoughFrench,German,AmericanandBritishpioneershaveallbeencreditedwiththeinventionofcinema,theBritishandthe
Theworldisgoingthroughthebiggestwaveofmergersandacquisitions(收购)everwitnessed.TheprocesssweepsfromhyperactiveA
最新回复
(
0
)