Graph AlgorithmsIntermediate

Kruskal's MST Algorithm

Greedy algorithm that builds a minimum spanning tree by adding edges in order of increasing weight, using union-find to avoid cycles. Efficient for sparse graphs with time complexity O(E log E). Applications include network design, clustering, approximation algorithms, and understanding greedy correctness proofs.

#graph#minimum-spanning-tree#greedy#union-find

Complexity Analysis

Time (Average)

O(E log E)

Expected case performance

Space

O(V)

Memory requirements

Time (Best)

O(E log E)

Best case performance

Time (Worst)

O(E log E)

Worst case performance

📚 CLRS Reference

Introduction to Algorithms•Chapter 23•Section 23.2

Implementation

Related Algorithms

View all in Graph Algorithms

Breadth-First Search (BFS)

Intermediate

Explores a graph level by level, visiting all vertices at the current depth before moving deeper. Uses a queue and is ideal for finding shortest paths in unweighted graphs. Applications include maze solving, social network analysis, and finding connections between nodes.

Depth-First Search (DFS)

Intermediate

Explores a graph by going as deep as possible along each path before backtracking. Implemented using a stack or recursion, making it natural for recursive problems. Used for pathfinding, cycle detection, topological sorting, and maze generation.

Dijkstra's Algorithm

Advanced

Finds the shortest paths from a single source vertex to all other vertices in a weighted graph. Powers GPS navigation systems and network routing protocols. Works efficiently with non-negative edge weights using a greedy approach with a priority queue.

Back to Graph Algorithms