Kruskal’s algorithm for the minimum spanning tree has a table equivalent. This is useful for large problems where drawing the network diagram would be hard or time-consuming. The table algorithm is also very suitable for automation.
Kruskal's table algorithm has the following steps.
-
Choose the smallest number (arc length) in the table. Cross out the rows for the vertices at each end of this arc.
-
Label the column containing this arc (1).
-
Look for the next minimum arc length in the table. Bracket it, cross out the row, label the column and carry on in this manner until all the columns are labelled.
-
The length of the minumum spanning tree is the sum of the bracketed numbers.
The distance table for the above network is
A
B
C
D
E
F
G
A
-
4
5
-
-
-
11
B
4
-
9
6
-
-
-
C
5
9
-
-
1
-
2
D
-
6
-
-
-
10
-
E
-
-
1
-
-
4
-
F
-
-
-
10
4
-
10
G
11
-
2
-
-
10
-
CE is the minimum length. Cross out rows C and E and label columns C and E as (1) and (2).
(1)
(2)
A
B
C
D
E
F
G
A
-
4
5
-
-
-
11
B
4
-
9
6
-
-
-
C
5
9
-
-
1
-
2
D
-
6
-
-
-
10
-
E
-
-
(1)
-
-
4
-
F
-
-
-
10
4
-
10
G
11
-
2
-
-
10
-
Now look for the smallest number free in the table. It is 2 in row G. Cross out row G and label column G as (3).
(1)
(2)
(3)
A
B
C
D
E
F
G
A
-
4
5
-
-
-
11
B
4
-
9
6
-
-
-
C
5
9
-
-
1
-
2
D
-
6
-
-
-
10
-
E
-
-
(1)
-
-
4
-
F
-
-
-
10
4
-
10
G
11
-
(2)
-
-
10
-
Look for the smallest free number in the table. We have a choice of the 4's in rows A, B or F. The next smallest entries in rows A, B and F are 5, 6 and 10 respectively. By picking row F to cross out we are keeping shorter lengths in rows A and B 'in the pot'. Cross out row F and label column F as (4).
(1)
(2)
(4)
(3)
A
B
C
D
E
F
G
A
-
4
5
-
-
-
11
B
4
-
9
6
-
-
-
C
5
9
-
-
1
-
2
D
-
6
-
-
-
10
-
E
-
-
(1)
-
-
4
-
F
-
-
-
10
(4)
-
10
G
11
-
(2)
-
-
10
-
The smallest free number is now 4. We have a choice of the 4's in the first or second row. The next smallest entries in rows A and B are 5 and 6 respectively. Cross out row B to keep the 5 available and label column B as 5.
(5)
(1)
(2)
(4)
(3)
A
B
C
D
E
F
G
A
-
4
5
-
-
-
11
B
(4)
-
9
6
-
-
-
C
5
9
-
-
1
-
2
D
-
6
-
-
-
10
-
E
-
-
(1)
-
-
4
-
F
-
-
-
10
(4)
-
10
G
11
-
(2)
-
-
10
-
The smallest free number is 4 in row A but picking this number would make a cycle (AB and BA)
The remaining smallest free number is 5 in row A. Cross out row A and label column A as (6).
(6)
(5)
(1)
(2)
(4)
(3)
A
B
C
D
E
F
G
A
-
4
(5)
-
-
-
11
B
(4)
-
9
6
-
-
-
C
5
9
-
-
1
-
2
D
-
(6)
-
-
-
10
-
E
-
-
(1)
-
-
4
-
F
-
-
-
10
(4)
-
10
G
11
-
(2)
-
-
10
-
Finally the smallest remaining number is 6 in row D. Cross out row D and label column D as (6). The minimum spanning tree is shown below.
