Discuss the Kruskal’s algorithm with example.

Question

Discuss the Kruskal&#8217;s algorithm with example.

Suresh Chand · Accepted Answer

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: List all the edges of G with non-decreasing order of their weights. Select an edge of minimum weight. This will be the first edge of T. 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. Repeat step 3 until n-1 edges have been selected. Example: 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. Pick edge (4,3): No cycle is formed, include it. Pick edge (2,7): No cycle is formed, include it. Pick edge (2,3): No cycle is formed, include it. Pick edge (7,4): Since including this edge results in cycle, discard it. Pick edge (4,5): No cycle is formed, include it. Pick edge (5,7): Since including this edge results in cycle, discard it. Pick edge (5,6): No cycle is formed, include it. Since the number of edges included equals (n– 1), the algorithm stops here.

Discuss the Kruskal’s algorithm with example.

Leave your Answer:

Hits Counter

Question

Discuss the Kruskal’s algorithm with example.

Leave your Answer: