Discuss the Kruskal’s algorithm with example.

Answers

This answer is not selected as best answer. This answer may not be sufficient for exam.

Your limit has been exceed. We have implemented this system because, We got difficulty on managing our servers. Please donate some amount to remove this limit.

Quota: 0 / 30

Donate

Kruskal’s Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which, we can traverse every vertex of the graph.

The Kruskal’s algorithm is given as follows:

  1. List all the edges of G with non-decreasing order of their weights.
  2. Select an edge of minimum weight. This will be the first edge of T.
  3. At each stage, select an edge of minimum weights from all remaining edges of G if it doesn’t form a cycle with previously selected edges in T. Then add the edge to T.
  4. Repeat step 3 until n-1 edges have been selected.

Example:

User Loaded Image | CSIT Guide

Edges of given graph with non-decreasing order of their weights:

(1, 6) (4, 3) (2, 7) (2, 3) (7, 4) (4, 5) (5, 7) (5, 6) (1, 2)
7 8 9 10 11 13 15 17 18

Pick edge (1, 6): No cycle is formed, include it.

User Loaded Image | CSIT Guide

Pick edge (4,3): No cycle is formed, include it.

User Loaded Image | CSIT Guide

Pick edge (2,7): No cycle is formed, include it.

User Loaded Image | CSIT Guide

Pick edge (2,3): No cycle is formed, include it.

User Loaded Image | CSIT Guide

Pick edge (7,4): Since including this edge results in cycle, discard it.

Pick edge (4,5): No cycle is formed, include it.

User Loaded Image | CSIT Guide

Pick edge (5,7): Since including this edge results in cycle, discard it.

Pick edge (5,6): No cycle is formed, include it.

User Loaded Image | CSIT Guide

Since the number of edges included equals (n– 1), the algorithm stops here.

If you found any type of error on the answer then please mention on the comment or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .