《离散数学》计算题求解:试求出如图所示赋权图中的最小生成树,并求此最小生成树的权。 5

 我来答
bill8341
高粉答主

推荐于2017-10-16 · 关注我不会让你失望
知道大有可为答主
回答量:1.8万
采纳率:95%
帮助的人:3630万
展开全部
求最小生成树的克鲁斯卡尔算法
①将带权连通图G=<n,m>的各边按权从小到大依次排列,如e1,e2,…,em,其中e1的权最小,em的权最大,m为边数。
②取权最小的两条边构成边集T0,即T0={e1,e2},从e3起,按次序逐个将各边加进集合T0中去,若出现回路则将这条边排除(不加进去),按此法一直进行到em,最后得到n-1条边的集合T0={e1,e2,…,en-1},则T0导出的子图就是图G的最小生成树。
梁洪铭06
2013-07-16 · TA获得超过202个赞
知道答主
回答量:44
采纳率:0%
帮助的人:59.9万
展开全部
可以参考:<a href="http://zhidao.baidu.com/question/560141123.html?from=pubpage&msgtype=2" target="_blank">http://zhidao.baidu.com/question/560141123.html?from=pubpage&msgtype=2</a>
虽然不是一道题,但解题思路是完全一样的,两种方法都有,很直观,很有效,您可以试试!
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
biubiubiujjja
2013-07-15 · TA获得超过414个赞
知道小有建树答主
回答量:399
采纳率:100%
帮助的人:293万
展开全部
能不能用数据结构的最小生成树的解法?
追问
可以,要求有步骤  和 解答过程
追答
那就简单了,1.将所有权值记录,取其中最小的权值,为v1-v7,保存;
2.在记录中删除v1-v7,取其中最小的权值,为v3-v4,保存;
3.在记录中删除v3-v4,取其中最小的权值,为v2-v7,保存;
4.在记录中删除v2-v7,取其中最小的权值,为v1-v2,但不是v1-v2最小权值,不保存;
5.在记录中删除v1-v2,取其中最小的权值,为v3-v7,保存;
6.在记录中删除v3-v7,取其中最小的权值,为v2-v3,但不是v1-v3最小权值,不保存;
7.在记录中删除v2-v3,取其中最小的权值,为v4-v7,但不是v1-v4最小权值,不保存;
8.在记录中删除v4-v7,取其中最小的权值,为v4-v5,保存;
9.在记录中删除v1-v2,取其中最小的权值,为v1-v6,保存;
至此最小生成树完成v1-v7,v1-v6,v7-v2,v7-v3,v3-v4,v4-v5
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
收起 1条折叠回答
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式