|
网站首页
|
业界新闻
|
小组
|
威客
|
人才
|
下载频道
|
博客
|
代码贴
|
在线编程
|
编程论坛
|
登录
注册
短消息
我发表的主题
我参与的主题
我收藏的贴子
我上传的附件
我下过的附件
编辑个人资料
我的博客
用户控制面板
搜索
道具
恢复默认风格
碧海青天
秋意盎然
棕红预览
粉色回忆
蓝雅绿
紫色淡雅
青青河草
e点小镇
橘子红了
红红夜思
水晶紫色
雪花飘飘
新年快乐
风格
短消息
论坛展区
帮助
编程论坛
→
开发语言
→
『 数据结构与算法 』
→ 最小生成树
我的收件箱(0)
欢迎加入我们,一同切磋技术
用户名:
密 码:
共有
2863
人关注过本帖
标题:
最小生成树
只看楼主
加入收藏
ivapple
等 级:
新手上路
帖 子:46
专家分:0
注 册:2008-7-31
楼主
收藏
问题点数:0 回复次数:16
最小生成树
对于一个各边权值均不相等的简单连通图,它的最小生成树唯一吗,
我感觉不唯一,可就是很难画出个图来验证,难道是唯一的,还请高手指点。
搜索更多相关主题的帖子:
成树
小生
2008-11-15 03:08
举报帖子
使用道具
赠送鲜花
geninsf009
等 级:
论坛游民
威 望:
8
帖 子:613
专家分:95
注 册:2008-8-16
第
2
楼
收藏
得分:0
在下不才,俺想请教一下"简单连通图"是啥子图?
我只知道简单路径这个概念,无向图连通与非连通的概念,
有向图的强连通的概念.
2008-11-15 23:07
举报帖子
使用道具
赠送鲜花
ivapple
等 级:
新手上路
帖 子:46
专家分:0
注 册:2008-7-31
第
3
楼
收藏
得分:0
没有自环和多重边的图叫简单图
2008-11-16 01:24
举报帖子
使用道具
赠送鲜花
ivapple
等 级:
新手上路
帖 子:46
专家分:0
注 册:2008-7-31
第
4
楼
收藏
得分:0
是不是应该说成连通的简单图好些
简单连通图在理解上有误导,会让人有“简单连通”和“复杂连通”的感觉。
2008-11-16 03:05
举报帖子
使用道具
赠送鲜花
geninsf009
等 级:
论坛游民
威 望:
8
帖 子:613
专家分:95
注 册:2008-8-16
第
5
楼
收藏
得分:0
直觉觉得可能是唯一的,不过可以考虑用反证法证明一下,
分析中...
2008-11-16 13:36
举报帖子
使用道具
赠送鲜花
ivapple
等 级:
新手上路
帖 子:46
专家分:0
注 册:2008-7-31
第
6
楼
收藏
得分:0
再多些人讨论啊?
2008-11-17 01:41
举报帖子
使用道具
赠送鲜花
ivapple
等 级:
新手上路
帖 子:46
专家分:0
注 册:2008-7-31
第
7
楼
收藏
得分:0
顶起
2008-11-29 03:15
举报帖子
使用道具
赠送鲜花
jdshaoheyi
等 级:
新手上路
帖 子:133
专家分:5
注 册:2008-11-6
第
8
楼
收藏
得分:0
对于一个各边权值均不相等的简单连通图,它的最小生成树唯一
2008-11-30 15:03
举报帖子
使用道具
赠送鲜花
jdshaoheyi
等 级:
新手上路
帖 子:133
专家分:5
注 册:2008-11-6
第
9
楼
收藏
得分:0
首先最小生成树是在n个节点构成的网中,选取n-1条边,可以建立一个连通图,现在假设,我们用普里姆算法或者是克鲁斯卡尔算法,计算出一棵最小生成树(记住你已经计算出了一个最小生成树了),现在你又有幸的到了一个最小生成树,和上一次计算出的权值和是一样的,但是要知道这棵最小生成树也只有n-1条边啊!也就是说第一次算出的最小生成树和第二次算出的生成树只有一条边不一样,那会发生什么事情呢?
2008-11-30 15:11
举报帖子
使用道具
赠送鲜花
geninsf009
等 级:
论坛游民
威 望:
8
帖 子:613
专家分:95
注 册:2008-8-16
第
10
楼
收藏
得分:0
"也就是说第一次算出的最小生成树和第二次算出的生成树只有一条边不一样"
-----------啥意思?怎么解释?我们只知道图中一共有
n个顶点,但不知道多少条边啊?请多多指教,
我感觉也应该是唯一的,可感觉很难证明,我在试图用
反证法证明.
2008-11-30 15:25
举报帖子
使用道具
赠送鲜花
17
1/2页
1
2
快速回复:
最小生成树
数据加载中...
关于我们
|
广告合作
|
编程中国
|
清除Cookies
|
TOP
|
手机版
编程中国
版权所有,并保留所有权利。
Powered by
Discuz
, Processed in 0.036385 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved