Variation of Kruskal's algorithm

Suppose G is an undirected graph with n vertices, there are weighted edges between each pair of vertices. Can you construct a tree in following structure:

v_1-v_2-v_3-...-v_n such that each node in the tree corresponding to a vertex in G and each node only has one child except the leaf. Also the total weight of the tree edges is minimized.

If use an algorithm similar to Kruskal's Algorithm: sort all weights of edges in the original graph in ascending order. Starts from the minimal weight edge, if add this edge does not violate the tree structure described above, then add this one in the final tree, otherwise, move on to the next.

Can this algorithm give the tree with minimal weights? If not, is it possible to find an algorithm to get this tree?

---

It can, but it may not. Consider a 4-node graph with edge weights as follows:

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

The minimal tree is ABCD with length 7, but your algorithm will always start with the (length 1) edge AC which is not part of the minimal tree required.

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

上一篇: 构建覆盖顶点特定子集的最小生成树

下一篇: Kruskal算法的变化