Kruskal 算法的变体

Question

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

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

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

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

Answer 1

可以，但也未必。考虑一个具有如下边权重的 4 节点图：

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

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