Graph Algorithms Mind Map
Algorithm & Systems VisualizationsEvery graph algorithms visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.
1. How the map is organized
Ask what the algorithm must produce, and you know its branch:
- Just which vertices are reachable, in what order? Traversal. Groups or an order of the whole graph (SCCs, topological order, Euler path): connectivity and order.
- A cheapest path? Exact, with weights: shortest paths. With a goal and a distance guess, often on a grid: heuristic search.
- A set of edges or an assignment? Cheapest edges joining everything: spanning trees. Capacities, pairs or colors: flow, matching, coloring.
- Asking how hard a problem is, not how to solve it? Certificates and reductions: complexity.
2. The branches side by side
| Branch | Main tool | Typical time | Output |
|---|---|---|---|
| Traversal | queue or stack | O(V + E) | visit order, BFS/DFS tree |
| Connectivity and order | DFS, indegree queue | O(V + E) | SCCs, topological order, Euler path |
| Shortest paths | priority queue, relaxation | Dijkstra O(E log V), Bellman-Ford O(VE), Floyd O(V³) | distances and parents |
| Heuristic search | priority queue on g + h | depends on h; best case near path length | one path to a goal |
| Spanning trees | priority queue or union-find | O(E log V) | minimum spanning tree |
| Flow, matching, coloring | augmenting paths, backtracking | Edmonds-Karp O(VE²); coloring NP-hard | flow, matching, colors |
| Complexity | certificate, reduction | verify in poly time; best known search 2ⁿ | NP-complete proof |
3. Five facts to remember
- BFS finds shortest paths only when every edge has the same cost.
- Dijkstra fails with negative edges; Bellman-Ford handles them and detects negative cycles.
- A* with an admissible heuristic (never overestimates) still returns a shortest path.
- A topological order exists only in a DAG; it is the reverse DFS finish order.
- Max flow equals min cut: the full edges of the min cut limit the flow.
See all graph algorithms pages in the index, or the other mind maps.