假设G是具有n个顶点的无向图，在每对顶点之间存在加权边 . 你能用以下结构构建一棵树：
v_1-v_2-v_3 -...- v_n，使得树中的每个节点对应于G中的顶点，并且每个节点仅具有除叶之外的一个子节点 . 树边缘的总重量也最小化 .
如果使用类似于Kruskal算法的算法：按升序对原始图中所有边的权重进行排序 . 从最小权重边缘开始，如果添加此边缘不违反上述树结构，则在最终树中添加此边缘，否则，继续前进到下一个 .
这个算法能否给出最小权重的树？如果没有，是否有可能找到一个算法来获得这棵树？
1 回答
它可以，但它可能不会 . 考虑具有边权重的4节点图，如下所示：
最小树是长度为7的ABCD，但是您的算法将始终以（长度1）边缘AC开始，该边缘AC不是所需的最小树的一部分 .