algorithm Kruskal's Algorithm
Remarks
Kruskal's Algorithm is a greedy algorithm used to find Minimum Spanning Tree (MST) of a graph. A minimum spanning tree is a tree which connects all the vertices of the graph and has the minimum total edge weight.
Kruskal's algorithm does so by repeatedly picking out edges with minimum weight (which are not already in the MST) and add them to the final result if the two vertices connected by that edge are not yet connected in the MST, otherwise it skips that edge. Union - Find data structure can be used to check whether two vertices are already connected in the MST or not. A few properties of MST are as follows:
- A MST of a graph with
nvertices will have exactlyn-1edges. - There exists a unique path from each vertex to every other vertex.
