# Discuss the Kruskal’s algorithm with example.

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

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:

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.