Discrete Mathematical Structures by Pearson

Trees 11-25

Example 2 Use Kruskal’s algorithm to determine the road network of minimal cost for eight

cities in Fig. 11.35 in thousands of rupees.

20

16

1616

16

16

6

6

4

5

6

a

g

h

f

de

b

c

Figure 11.35

Solution:

Step 1: The arrangement of edges in increasing order of their weights is as follows:

Weight 4 5 6 6 6 16 16 16 16 16 20

Edge (a, g) (g, f

) (h, g) (b, c) (e, h) (a, b) (b, h) (c, d) (e, d) (f, e) (e, c)

Step 2: Choose edge (a, g) since it has smallest weight and include in T.

Step 3: An edge with next the smallest weight is (g, f ) since it does not form a cycle with the

edge in T and hence include it in T.

Step 4: An edge with next the smallest weight is ...