algorithm - Kruskal 算法的变体

Question

假设G是一个有n个顶点的无向图，每对顶点之间有加权边。你能按以下结构构造一棵树吗:

v_1-v_2-v_3-...-v_n 使得树中的每个节点对应于 G 中的一个顶点，并且每个节点除叶子外只有一个子节点。树边的总权重也被最小化。

如果使用类似于 Kruskal 算法的算法:将原始图中所有边的权重按升序排序。从最小权重的边开始，如果添加这条边不违反上面描述的树结构，则将这条边添加到最终树中，否则继续下一条。

这个算法能给树赋予最小的权重吗？如果不是，是否可以找到一种算法来得到这棵树？

Answer 1

可以，但也不一定。考虑一个具有如下边权重的 4 节点图:

AB:   3
AC:   1
AD: 100
BC:   2
BD: 100
CD:   2

最小树是长度为 7 的 ABCD，但您的算法将始终从(长度为 1)边 AC 开始，它不是所需最小树的一部分。