Graph Algorithms

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.

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.

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.

A best-first search algorithm that finds the shortest path using heuristics. Combines Dijkstra's algorithm and greedy best-first search using f(n) = g(n) + h(n). Widely used in games, robotics, and GPS navigation for efficient pathfinding.

Finds the Minimum Spanning Tree (MST) of a weighted undirected graph. Uses a greedy approach by sorting edges by weight and adding them if they don't create a cycle. Employs Union-Find for efficient cycle detection. Essential for network design and clustering.

Finds the Minimum Spanning Tree (MST) by growing a tree from a starting vertex. Always adds the minimum weight edge connecting a vertex in the tree to one outside. Uses a priority queue for efficient edge selection. Ideal for dense graphs.

Orders vertices of a Directed Acyclic Graph (DAG) such that for every edge u→v, u comes before v. Uses DFS-based approach. Essential for dependency resolution, build systems, and course scheduling.

Google's algorithm for ranking web pages by link structure. Computes importance scores iteratively.

Also known as the 'tortoise and hare' algorithm, this elegant technique detects cycles in linked lists or sequences using O(1) space. Uses two pointers moving at different speeds—if there's a cycle, they will eventually meet. Essential for detecting infinite loops, analyzing graph structures, and validating data integrity.

Single-source shortest path algorithm that handles negative weights and detects negative cycles. Relaxes all edges V-1 times to guarantee correct distances even with negative weights. Essential for currency arbitrage detection, network routing with varied costs, and situations where Dijkstra's algorithm fails. Trades speed for flexibility.

All-pairs shortest path algorithm that computes distances between every pair of vertices in O(V³) time. Uses dynamic programming with elegant three-line core logic. Handles negative weights and provides transitive closure. Ideal for dense graphs, network analysis, and when all pairwise distances are needed.

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.

Greedy algorithm that grows a minimum spanning tree by repeatedly adding the cheapest edge connecting the tree to a new vertex. Uses a priority queue for efficiency with O(E log V) time. Preferred for dense graphs and real-time applications like network broadcasting and circuit design.