What do you mean by MST. Explain Kruskal Algorithm with example.

This answer is restricted. Please login to view the answer of this question.

Login Now

MST stands for  Minimum Spanning Tree. MST is a connected weighted graph that has the smallest possible sum of weight of its edges.

Kruskal’s Algorithm:

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:

- Hamro CSIT

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.

- Hamro CSIT

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

- Hamro CSIT

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

- Hamro CSIT

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

- Hamro CSIT

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

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

- Hamro CSIT

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

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

- Hamro CSIT

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 report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .