以下伪代码来自The Algorithm Design Manual的在线预览版本的第一章(本PDF第7页).
这个例子是一个有缺陷的算法,但我仍然想要理解它:
[...]一个不同的想法可能是重复连接最接近的一对端点,这些端点的连接不会产生问题,例如过早终止循环.每个顶点都以其自己的单个顶点链开始.在将所有内容合并在一起之后,我们将最终得到一个包含其中所有点的链.连接最后两个端点为我们提供了一个循环.在执行此最近对启发式过程中的任何步骤中,我们将有一组可用于合并的单顶点和顶点不相交链.在伪代码中:
ClosestPair(P)
Let n be the number of points in set P.
For i = 1 to n ? 1 do
d = ?
For each pair of endpoints (s, t) from distinct vertex chains
if dist(s, t) ? d then sm = s, tm = t, and d = dist(s, t)
Connect (sm, tm) by an edge
Connect the two endpoints by an edge
请注意,sm并且tm应该s …