For Single-Link Clustering

Step 1

Begin with the disjoint clustering, which places each object in its own cluster. Find an MST on G( ).

Repeat steps 2 and 3 until all objects are in one cluster.

Step 2

Merge the two clusters connected by the MST edge with the smallest t weight to define the next clustering.

Step 3

Replace the weight of the edge selected in step 2 by a weight la rger than the largest proximity.

A divisive algorithm is just as simple. Cut the edges in the MST in the order of weight, cutting the largest first. Each cut defines a new clustering, with those objects connected in the MST at any stage belonging to the same cluster. As long as no proximity ties occur, these algorithms generate the same single-link clusterings as the earlier algorithms.