37

Paper 1 – Kruskal ’ s Algorithm

Example

The following cost adjacency matrix shows the information of a graph with five vertices

A , B , C , D and E :

	A	B	C	D	E
A	-	30	26	48	52
B	30	-	40	26	22
C	26	40	-	24	32
D	48	26	24	-	40
E	52	22	32	40	-
Kruskal ’ s algorithm is used to find the minimum spanning tree for this graph .

( a ) State the edge of the smallest cost .

( b ) By using the algorithm , find the minimum spanning tree .

( c ) Write down the cost of the minimum spanning tree .

[ 1 ]

[ 3 ]

[ 1 ]

Solution

( a ) BE A1

( b )	For any two edges correct		A1
	For all edges correct		A1
1 .		Choose BE of cost 22
2 .		Choose CD of cost 24
3 .		Choose AC of cost 26
4 .		Choose BD of cost 26
Thus , the minimum spanning tree is a tree
containing BE , CD , AC and BD .			A1

( c ) 98 A1

[ 1 ]

[ 3 ]

[ 1 ]

128

SE Production Limited