Kruskal's Algorithm

Introduction

• Purpose: To find the minimum cost spanning tree (MCST).
• Usage: Utilized in competitive exams, college, and university exams.
• Alternatives: Prim's Algorithm.

Spanning Tree Basics

• Spanning Tree Properties:
  • The number of vertices is the same as the original graph.
  • Number of edges = N - 1 (vertices - 1).
  • No cycles (loops) and must be connected.

Steps in Kruskal's Algorithm

1. List edges by increasing weight: Arrange edges in ascending order of their weights.
2. Include minimum weight edges: Start including edges from the smallest weight without forming a cycle.
3. Check for cycles: Make sure that addition of a new edge does not form a cycle.
4. Repeat until N - 1 edges are included: Continue adding edges until the graph has N - 1 edges.

Example Walkthrough

1. Initial Setup: Graph with vertices 1-7, arrange edges by weights.
2. Edge Selection: Add edges one by one (e.g., B-E, A-C, E-F, B-C, E-G), avoid cycles such as F-G.
3. Result: Sum of edge weights for MCST is 21.

Comparison to Prim's Algorithm

• Connection: Kruskal’s algorithm can have disconnected intermediate steps, Prim's always remains connected.
• Result: Both algorithms yield the same MCST but operate differently.

Time Complexity

1. MinHeap Construction: For E edges, use MinHeap requiring O(E) or E log E time.
2. Edge Extraction & Union-Find:
   • Extract MinEdge and add to the spanning tree. Ensure no cycle formation.
   • Best Case: O((N-1) log E) where N is vertices.
   • Worst Case: O(E log E) for considering all edges.

Key Points to Remember

• Avoid cycles while adding edges even if they have minimum weight.
• Properly handle disconnections in intermediate stages in Kruskal’s method.
• Be cautious with graphs designed to create confusion.

Complexity Analysis

• Construction: Using heapify - O(E), without heapify - E log E.
• Insertion: Each insertion - log E,
  • Best Case: N-1 insertions.
  • Worst Case: E insertions (All edges might need to be checked).

Conclusion

• Relevance: Widely asked in exams.
• Difficulty: Easy to understand but care needed in avoiding cycles and managing heap operations.

Thank You