What is the meaning of “from distinct vertex chains” in this nearest neighbor algorithm?

This is how I see it, after explanation of Ernest Friedman-Hill (accepted answer):

So the example from the same book (Figure 1.4).
I’ve added names to the vertices to make it clear
Figure 1.4

So at first step all the vertices are single vertex chains, so we connect A-D, B-E and C-F pairs, b/c distance between them is the smallest.

At the second step we have 3 chains and distance between A-D and B-E is the same as between B-E and C-F, so we connect let’s say A-D with B-E and we left with two chains – A-D-E-B and C-F

At the third step there is the only way to connect them is through B and C, b/c B-C is shorter then B-F, A-F and A-C (remember we consider only endpoints of chains). So we have one chain now A-D-E-B-C-F.

At the last step we connect two endpoints (A and F) to get a cycle.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)