Prim's Algorithm in Table Form

Prim’s algorithm for the minimum spanning tree has an equivalent table algorithm. This is useful for large problems where drawing the network diagram would be hard or time-consuming.

Prim's table algorithm has the following steps.

1. Choose a starting vertex. Cross out the row corresponding to this node.

2. Label the column corresponding to this node (1). Look for the minimum number in column (1) and put brackets around it.

3. Cross out the row of this minimum value and label the corresponding column (2).

4. Look for the minimum number in columns (1) or (2). Bracket it, cross out the row, label the column and carry on in this manner until all the columns are labelled.

5. The length of the minimum spanning tree is the sum of the bracketed numbers.

The distance table for the above network is

The minimum spanning tree will have the same length whatever node we start from. It is after all, the minimum. I will start from C, because CE is the minimum length.

The smallest number free in column (1) in column (1) is 1, corresponding to E. Cross out row E and label column E as (2).

Now look for the smallest number free in either column (1) or (2). It is 2 in row G. Cross out row G and label column G as (3).

Look for the smallest free number in columns (1), (2) or (3). It is 4 in row F. Cross out row F and label column F as (4).

Look for the smallest free number in columns (1), (2), (3) or (4). It is 5 in row A. Cross out row A and label column A as (5).

The smallest free number in columns (1), (2), (3), (4) or (5) is 4 in row B. Cross out row B and label column B as (6).

The smallest free number in columns (1), (2), (3), (4), (5) or (6) is 6 in row D. Cross out row D and label column D as (7).

The length of the minimum spanning tree is 1+2+4+4+5+6=22.