MST Construction (Prim’s or Kruskal’s)

What is a Minimum Spanning Tree ?

• A minimum spanning tree is a subset of edges such that the sum of edge weights is minimum
• A MST is constructed for an undirected weighted graph.
• A MST does not form a Cycle.
• All edges are. included only once

Complexity: O ( V log E )

Prim’s Algorithm

Kruskal’s Algorithm

Points to remember:

• This uses the union-find algorithm to construct the MST edge by edge.