0
1.8kviews
Draw the minimum cost spanning tree using Kruskals algorithm. Also find its cost with all intermediate steps
1 Answer
0
14views
written 8.5 years ago by |
A minimum spanning tree can be defined as a spanning tree with weight less than or equal to the weight of every other spanning tree.
Let us find the minimum spanning tree for the given graph.
Step 1: Remove all loops
Here as no loops are present, we skip this step.
Step 2: Remove all Parallel edges(i.e edges having multiple values)
If so eliminate the edge with highest value and keep the one with least value intact. Here since such edges are not present, we skip this step.
Step 3: Sort the edges according to minimum weights.
Edge | Value |
---|---|
A-D | 1 |
E-F | 2 |
C-E | 3 |
E-D | 4 |
C-D | 5 |
D-F | 5 |
A-C | 6 |
A-B | 7 |
C-B | 8 |
Step 4: Construct minimum spanning tree.
Here we go from top to bottom of the above table by joining the given edges. An edge is discarded is it results in a cycle formation.
ADD COMMENT
EDIT
Please log in to add an answer.