geeksforgeeks上的做法:
-
Start with a subtree T consisting of
one given terminal vertex
-
While T does not span all terminals
a)
Select a terminal x not in T that is closest to a vertex in T.
b) Add to T the shortest path that connects x with T
翻译过来就是:
1)以一个给定点集 S 中的任意一点为斯坦纳树的点集 T 中的初始点。
2)当 T 中的点没有包括所有 S 中的点,我们执行以下操作:
选择S中的离集合T最近的点。然后将其最短路径上的点加入集合T中。