主题：数据结构 最小生成树问题
寂寞の风
[专家分：130] 发布于 2006-05-14 17:02:00
请问大哥大姐们，图的编历中，如何编历最小生成树？
回复列表 （共5个回复）
沙发
euc [专家分：4310] 发布于 2006-05-14 18:36:00
把最小生成树当图就好了呗.
板凳
寂寞の风 [专家分：130] 发布于 2006-05-18 08:07:00
可如何编啊? 总不可能当图一样编吧~
3 楼
catherienangel [专家分：140] 发布于 2006-05-18 10:26:00
看一下数据结构书呀，有算法思想的，最小生成树不是有普里姆和克里斯卡尔算法吗，前者对应边稠密，后者为边稀疏的
4 楼
sk8erboy [专家分：10] 发布于 2006-05-30 01:14:00
5588077）
5 楼
rickone [专家分：15390] 发布于 2006-06-01 14:45:00
好像问得有问题,图遍历和求最小生成树是两个问题,遍历最小生成树=遍历树=遍历图,树的定义是连通无环的图,特殊的图.
求最小生成树的算法书上有两个一个是规划点集O(n*n),一个是构造最小边集O(mlogm),而做为连通图有关系n-1<=m<=n(n-1)/2,后一个算法的复杂度变动为O(nlogn)~O(n*nlogn),而O(n*n)在它们之间,就看是稀疏边还是稠密边了.
我来回复
您所在位置：