Kruskal's Algorithm

Kruskal’s Algorithm Code

Steps:

1. Sort Edges: Arrange all edges in non-decreasing order of their weights.
2. Initialize Forest: Start with a forest (each vertex is an individual tree).
3. Edge Selection:
   • Pick the smallest edge.
   • Check if adding this edge forms a cycle using Union-Find.
   • If not, include it in the MST.
4. Repeat: Continue until there are V-1 edges in the MST (V is the number of vertices).

Data Structures:

• Disjoint Set (Union-Find): To check for cycles efficiently.
• Priority Queue (Min-Heap): For sorting edges by weight.

Complexity

• Complexity: $O(E \log E)$ or $O(E \log V)$.
• Sorting edges: priority queue heap sort = $O(E \log E)$.
• Union-Find: $O(\log V)$ per edge for cycle check. Near constant due to path compression.
• Overall: $O(E \log E)$; $E ≤ V^2$ for dense graph, so also $O(E \log V)$.

Prim's Algorithm

Prim’s Algorithm Code

Steps:

• Similar to Dijkstra’s; But at each greedy operation, we find vertex with min key value, instead of vertex with min distance to source
• Key value: minimum weight edge connecting a vertex to the already included vertices.