Kruskal算法的变分
Kruskal算法的变分
提问于 2016-01-26 20:41:33
设G是一个具有n个顶点的无向图，每对顶点之间都有加权边。您能否按以下结构构造一棵树：
V_1-v_2-v_3-.-v_n使得树中每个节点对应于G中的一个顶点，并且每个节点只有一个子节点，除了叶子。此外，树边的总重量被最小化。
如果使用类似于Kruskal算法的算法:按升序排序原始图中的所有边的权重。从最小权重边开始，如果添加此边不违反上面描述的树结构，那么将其添加到最后一棵树中，否则，转到下一个。
该算法能给出权值最小的树吗？如果没有，是否有可能找到一种算法来得到这棵树？
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-01-26 20:52:42
可以，但可能不行。考虑一个具有边权的4节点图，如下所示：
AB: 3
AC: 1
AD: 100
BC: 2
BD: 100
CD: 2最小树是长度为7的ABCD，但是算法总是从(长度1)边AC开始，这不是最小树的一部分。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35029034
复制相关文章
相似问题
腾讯云开发者
