Question

Using the graph below, create a minimum cost spanning tree using Kruskal's Algorithm and report it's total weight. 

The Spanning Tree has a total Weight of _______ 

Answer 1

Step-1

Note the arc weights and sort the list as per non-decreasing order as follows:

Arc	Weight
W-N	65
C-W	80
S-F	105
D-C	120
O-W	130
C-N	130
F-D	140
O-C	150
F-A	155
A-D	160
O-N	190
F-C	200
D-W	220
S-C	230
O-D	230
D-N	250
S-A	265
A-O	305

Step-2:

Include the arc in the spanning tree from the top of the list moving downwards. Reject an arc if a closed loop is formed. Stop when all the nodes have been included in a single spanning tree.

Arc	Weight	Reject \ Accept	Reason for rejection
W-N	65	Accept
C-W	80	Accept
S-F	105	Accept
D-C	120	Accept
O-W	130	Accept
C-N	130	Reject	Closed-loop C-W-N-C
F-D	140	Accept
O-C	150	Reject	Closed-loop O-C-W-O
F-A	155	Accept & STOP
Total weight	1075