首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
admin
2019-01-16
18
问题
“破圈法”是“任取一圈,去掉圈上权最大的边”,反复执行这一步骤,直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法,并用程序实现你所给出的算法。(注意:圈就是回路)
选项
答案
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条边:顶点,权值 seanf(”%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条边若仍连通 f edge[k].W=0;eg--;} //测试下一条边edge[k],权值置0表示该边被删除 k++; //下条边 }//while } connect()是测试图是否连通的函数,可用DFS函数或BFS函数实现,若是连通图,一次进入DFS函数或BFS函数就可遍历完全部顶点,否则,因为删除该边而使原连通图成为两个连通分量时,该边不应删除。“破圈”结束后,可输出edge中W不为0的n一1条边。
解析
转载请注明原文地址:https://kaotiyun.com/show/flRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
阅读材料,回答问题:材料一:战后美国对一些新兴工业部门、重大科研项目、现代化公共设施等投入大量资金,如美国时发展原子能工业的投资,从1945年到1970年共计达175亿美元。美国还通过国家力量来扩张国外市场,从50年代中期起,为加强国际市场的竞争力,政府
根据越南战争的起源和发展,分析“冷战”时期美国对第三世界政策的目标和动机。
简述雅典民主政治的形成过程、主要内容和历史局限性。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
在下列四本部书中有可能记载“甘薯所在,局面便有半年之粮,民间渐次广种”一语的只能是()。
编写一个算法,实现以较高的效率从有序顺序表A中删除其值在x和y之间x≤A[i]≤y的所有元素。
就绪队列中有n个进程等待使用一个CPU,那么,如果采用不同的调用算法,就有()种调度顺序。
对下列4个序列用快速排序方法进行排序,以序列的第1个元素为基准进行划分。在第1趟划分过程中,元素移动次数最多的是()。
假设在一台单处理机上执行如下表所示的进程,且假定这些进程在时刻0以1,2,3,4,5的顺序创建。时间单位为时间片,优先级以数值大者为优。(1)请说明分别使用FCFS、RR(时间片=1)、SPF以及非抢夺式优先级调度算法时,这些进程的执行
随机试题
恒发公司为在上海证券交易所主板挂牌的上市公司,明方公司持有恒发公司30%的股份,是其控股股东。2018年8月,明方公司管理层与朱亚集团接触,拟将其持有的恒发公司全部股份转让给朱亚集团。8月16日,市场出现传闻,称明方公司拟将其持有的恒发公司股份售出以偿还
患者女性,74岁。腰背部疼痛六个月前来就诊,体检:肝肋下2cm,脾肋下3cm,多个腰椎骨压痛明显。实验室检查:血红蛋白85g/L,白细胞4.6×10。9/L,血小板110×109/L,血沉120mm/h,尿蛋白定性(﹢),24小时尿蛋白定量5g。BUN15
既可以清肺火、清胃火,又可泻肾火的中药是
考虑诊断为化疗后10天死亡,最可能的死亡原因是
A.青霉素GB.氨基糖苷类C.大环内酯类D.头孢菌素类E.四环素类治疗流行性脑脊髓膜炎宜首选
对于已经生效的合同,如发现合同条款空缺,致使合同难以履行,则对于合同有关内容的确定方法,下列表述中正确的是( )。
若f(x)=,则f"(0)=
法律所具有的、通过其规定和实施而影响人们思想,培养和提高人们法律意识,引导人们依法行为的作用。这是法律规范的
下列叙述中错误的是
BonAppetiteA)Wealllovethefoodwegrowupon,butwealsoseekadventureinthefoodwehavenevertasted.Ahugelypopular
最新回复
(
0
)