Kruskal算法的变化

2018-06-12 07:45:17

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

v_1-v_2-v_3 -...- v_n，使得与G中的顶点相对应的树中的每个节点以及每个节点仅具有除叶子之外的一个子元素。而且树边缘的总重量也被最小化了。

如果使用类似Kruskal算法的算法：按照升序对原始图中的所有边的权重进行排序。从最小权重边开始，如果添加此边不违反上述树结构，则将其添加到最终树中，否则，转到下一个。

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

它可以，但它可能不会。考虑一个具有边权重的4节点图，如下所示：

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

最小的树是长度为7的ABCD，但是你的算法总是以（长度为1）边AC开始，这不是所需的最小树的一部分。

链接地址: http://www.djcxy.com/p/35257.html