Data Structures and Algorithms - Old Questions
13. Discuss the Kruskal's algorithm with example.
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.
|
(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.