Introduction

In graph theory, a Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-weighted graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. The MST is an essential concept in various fields such as computer networks, civil engineering, and electronics, where the goal is to minimize the cost of connecting a set of nodes.

There are several algorithms to find a minimum spanning tree of a graph. In this article, we will explore the different algorithms used to find MSTs, including their implementations, advantages, and complexities.

Kruskal's Algorithm

Kruskal’s Algorithm is a greedy algorithm that finds an MST for a connected weighted graph. It operates by sorting all the edges of the graph by weight and adding them one by one to the MST, provided they do not form a cycle.

Steps in Kruskal’s Algorithm

1. Sort all the edges in non-decreasing order of their weight.
2. Create a forest, where each node is a separate tree.
3. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If not, include this edge in the MST. If it forms a cycle, ignore it.
4. Repeat step 3 until there are (V-1) edges in the spanning tree, where V is the number of vertices.

Implementation

• Time Complexity: $O(E \log E + E \log V)$, where E is the number of edges and V is the number of vertices. Sorting of edges requires $O(E \log E)$ time and the find and union operations take logarithmic time.
• Space Complexity: $O(V + E)$
• Time Complexity: $O(V^2)$ when using an adjacency matrix for storing graph.
• For graphs represented as adjacency lists, Prim's algorithm can be optimized using a priority queue to achieve a time complexity of $O(E \log V)$.
• Space Complexity: $O(V)$
• Time Complexity: $O(E \log V)$
• Space Complexity: $O(V)$