这个最近邻算法中"来自不同顶点链"的含义是什么？

Question

以下伪代码来自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应该sm和tm.

首先,我不明白"来自不同的顶点链"意味着什么.其次,i在外循环中用作计数器,但i它本身从未在任何地方使用过!有人比我更聪明,请解释这里真正发生了什么？

Answer 1

在解释了欧内斯特·弗里德曼 - 希尔(接受的答案)之后,我就是这样看的:

所以来自同一本书的例子(图1.4).我已经为顶点添加了名称以使其清晰

所以在第一步所有顶点都是单顶点链,所以我们连接AD,BE和CF对,它们之间的b/c距离最小.

在第二步,我们有3个链,AD和BE之间的距离与BE和CF之间的距离相同,所以我们连接让我们说AD与BE,我们留下两个链 - ADEB和CF

在第三步,连接它们的唯一方法是通过B和C,b/c BC比BF,AF和AC短(记住我们只考虑链的端点).所以我们现在有一条连锁店ADEBCF.

在最后一步,我们连接两个端点(A和F)以获得一个循环.

Answer 2

1)描述表明每个顶点总是属于"单顶点链"(即,它是单独的)或它属于另一个链; 顶点只能属于一个链.该算法在每个步骤中说明您选择每个可能的两个顶点对,每个顶点都是它们所属的相应链的端点,并且不属于同一个链.有时候他们会成为单身人士; 有时一个或两个已经属于一个非平凡的链,所以你将加入两个链.

2)你重复循环n次,这样你最终选择每个顶点; 但是,实际的迭代计数不用于任何事情.重要的是你运行循环足够多次.