Nearest-neighbor chain algorithm: Difference between revisions

Revision as of 22:29, 28 October 2016

Revision as of 00:44, 29 October 2016

Line 66:

**Otherwise, if {{mvar|D}} is not already in {{mvar|S}}, push it onto {{mvar|S}}.

If thereit mayis possible that there beare multiple equal nearest neighbors to a cluster, then the algorithm requires a consistent tie-breaking rule:. forFor instance, inone thismay case,assign thearbitrary nearestindex neighbornumbers mayto beall chosen, amongof the clusters at equal minimum distance from {{mvar|C}}, by numbering the clusters arbitrarily and choosing the one with the smallest index.

and then select (among the equal nearest neighbors) the one with the smallest index number. This rule prevents certain kinds of inconsistent behavior in the algorithm; for instance, without such a rule, the neighboring cluster {{mvar|D}} might occur earlier in the stack than as the predecessor of {{mvar|C}}.

==Time and space analysis==