Chapter 12.3, Problem 12E

In our discussion of the complexity of Kruskal’s algorithm, with suggested a certain system of labeling vertices (p.386). Consider the following modification.

Suppose that vertex x is labeled k and vertex y is labeled l and that we have just selected edge xy. Compose the relative sizes of the components to which x and y belong, and change the labels of all vertices in the smaller of these components to the label of the larger. (if the components have equal size, label of the larger. (If the components have equal size, label with smaller number.)

With reference to Example 2. (p. 384), we begin with 13 components each containing a single vertex. After the selection of AJ, component 1 contains two vertex, A and J and component 10 is empty; the remaining components change as the edges GM, DE, MF, and FE are successively selected.

1. Continue the scheme shown in this figure to show the relabeling of vertices until the spanning tree of Fig. 12.16 is obtained.

2. [BB] Show that in the general case the number of times the label on any vertex is changed is at most log₂ n, n the number of vertices of G.

3. [BB] show that Kruskal’s algorithm can be implemented with a number of comparisons that is $\text{O}\left(\text{N log N}\right),$N the number of edges of G.