Graph algorithms, step by step
Graph algorithms are easiest to learn by watching the frontier grow. Every topic here animates the visited set, the queue or heap, and the distances as they change.
Learn BFS and DFS first: Dijkstra is BFS with a priority queue, and A* is Dijkstra with a heuristic.
Start with Breadth-First Search (BFS) 11 topics
Traversal
- Breadth-First Search (BFS)A fundamental graph traversal algorithm. It explores all neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. It guarantees the shortest path in an unweighted graph.Beginner25m
- Depth-First Search (DFS)Explore graphs by going deep! Unlike BFS, DFS dives into the graph structure. Essential for detecting cycles, topological sort, and maze solving.IntermediateCode20m
- Topological SortOrder tasks with dependencies! Visualize Kahn's Algorithm using In-Degrees. Crucial for build systems, course scheduling, and resolving dependencies.IntermediateCode25m
Shortest paths
From unweighted to negative edges.
- 0-1 BFS (Deque Optimization)Shortest path when edge weights are only 0 or 1. Uses deque instead of priority queue for O(V+E) instead of O(E log V). Critical for grid problems with obstacles.Advanced25m
- Dijkstra's AlgorithmA popular algorithm for finding the shortest path between nodes in a graph. It handles weighted edges and guarantees the shortest path for non-negative weights.Advanced30m
- A* SearchAn informed search algorithm that uses heuristics to guide the search. It guarantees the shortest path (if heuristic is admissible) and is usually much faster than Dijkstra.Advanced30m
- Bellman-Ford AlgorithmFind shortest paths from a source to all vertices, even with negative edge weights. Can also detect negative weight cycles.Advanced30m
- Floyd-Warshall AlgorithmFind shortest paths between ALL pairs of vertices. Works with negative weights (but no negative cycles). Simple triple-nested loop.Advanced30m
Connectivity and structure
- Union-Find (Disjoint Set)Master the Union-Find data structure. Essential for Kruskal's Algorithm, connected components, and cycle detection in undirected graphs.IntermediateCode20m
- Minimum Spanning Tree (Kruskal's Algorithm)Visualize Kruskal's MST algorithm: sort all edges by weight, then greedily add the cheapest edges that don't create a cycle using Union-Find. Demonstrates why a greedy approach guarantees a minimum spanning tree on connected graphs.Advanced35m
- Graph Coloring (Greedy)Assign colors to vertices such that no two adjacent vertices share the same color. The greedy approach gives an upper bound on the chromatic number.Intermediate25m