Minimum Spanning Tree (MST)

A spanning tree is a tree that connects all the vertices of a graph through some edges. If a graph has N vertices, then its spanning tree will have N-1 edges. A minimum spanning tree is a spanning tree of a weighted graph with the minimum total edge weight. the lightest edge plays a crucial role in finding the MST. There are two algorithms for finding minimum spanning trees: Kruskal's algorithm and Prim's algorithm.

Applications:

• Communication networks
• Transportation networks

Prim's Algorithm

• Prim's algorithm uses a greedy strategy.
• It starts with an arbitrary vertex v and chooses the minimum edge that connects v to a new vertex w.
• This process is repeated until the minimum spanning tree (MST) is found.
• Utilizes a binary heap to store the edges outside clusters.
• The running time is O(E log V) since the graph is connected.
• The space complexity is either O(E + V) using a binary heap or O(V) using a Fibonacci heap.

Kruskal's Algorithm

• Scans the edges only once.
• Works with disconnected graphs
• Ensures that the result is a tree with no cycles.
• Utilizes a priority queue to store the edges outside clusters.
• Maintains a forest of trees.
• The running time is O(E log E) or O(E log V), whichever is smaller.
• The space complexity for storing the graph and the disjoint-set data structure is O(V + E).