Minimum Spanning Tree Using Kruskal’s algorithm
Given a weighted, undirected and connected graph. The task is to find the sum of weights of the edges of the Minimum Spanning Tree
Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.
Spanning Tree – A tree that spans all the vertices of a connected and undirected graph .
Spanning Tree Properties
- for graph G(V, E), it contains exact (V-1) edges
- Remove (E-V+1) edges
- Maximally acyclic – Means after adding an edge will be cycle
- Minimally connected – means removable of an edge from spinning tree it will give more than one components
- maximum possible spinning tree is V ^ (V-2)
Solution:
- In Kruskal’s algorithm use disjoint set with find – union operation
- its greedy
Algorithm
- Take all edges
- Sort edges in ascending order
- Iterate all edges one by one
- find disjoint set of source vertex of edge
- find disjoint set of destination vertex of edge
- if both sets are different then,
- add edge to output list
- union both sets
- return output list of edge
Latest Source Code:
Github: MinimumSpanningTreeKruskalAlgorithm.java
Output:
Minimum Spanning Tree Edges: 0 - 1 --> 2 1 - 2 --> 3 1 - 4 --> 5 0 - 3 --> 6