A Level Maths Notes: D1 – Prim's Algorithm in Table Form



Prim’s algorithm for the minimum spanning tree is also suitable for use on distance tables, or the equivalent for the problem. This is useful for large problems where drawing the network diagram would be hard or time-consuming.

That tables can be used makes the algorithm more suitable for automation than Kruskal’s algorithm. The reason for this is that the data used would have to be sorted to be used with Kruskal’s algorithm. With Prim’s algorithm, however, it is only the minimum value that is of interest, so no sorting is normally necessary.

Prim's algorithm has the following steps.

  1. Choose a starting node. 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. Find the node of this row 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 minumum spanning tree is the sum of the bracketed numbers.

The distance table for the above table 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

-



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 BC is the minimum length.



(1)






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 number free in column (1) in column (1) is 1, corresponding to E. Cross out row E and label column E as (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 either column (1) or (2). 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 columns (1), (2) or (3). It is 4 in row F. 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

-


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).

(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 in columns (1), (2), (3), (4) or (5) is 4 in row B. Cross out row B and label column B as (6).

(5)

(6)

(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 in columns (1), (2), (3), (4), (5) or (6) is 6 in row D. Cross out row D and label column D as (7).

(5)

(6)

(1)

(7)

(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 length of the minimum spanning tree is 1+2+4+4+5+6=22

Home Maths and Physics Notes Home A Level Maths Notes Home D1 Maths Notes Home


Student Forum Tutor Agency