algorithm - 这个最近邻算法中的 "from distinct vertex chains"是什么意思？

Question

以下伪代码来自算法设计手册在线预览版的第一章(第 7 页来自 this PDF)。

这个例子是一个有缺陷的算法，但我仍然很想理解它:

[...] A different idea might be to repeatedly connect the closest pair of endpoints whose connection will not create a problem, such as premature termination of the cycle. Each vertex begins as its own single vertex chain. After merging everything together, we will end up with a single chain containing all the points in it. Connecting the final two endpoints gives us a cycle. At any step during the execution of this closest-pair heuristic, we will have a set of single vertices and vertex-disjoint chains available to merge. In pseudocode:

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

在 Ernest Friedman-Hill 的解释(接受的答案)之后，我是这样看的:

所以来自同一本书的示例(图 1.4)。我已将名称添加到顶点以使其清晰

所以第一步所有的顶点都是单顶点链，所以我们连接 A-D、B-E 和 C-F 对，它们之间的 b/c 距离最小。

在第二步，我们有 3 条链，A-D 和 B-E 之间的距离与 B-E 和 C-F 之间的距离相同，所以我们连接 A-D 和 B-E，剩下两条链 - A-D-E-B 和 C-F

在第三步，连接它们的唯一方法是通过 B 和 C，b/c B-C 比 B-F、A-F 和 A-C 更短(记住我们只考虑链的端点)。所以我们现在有一条链 A-D-E-B-C-F。

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