Chapter 3: Graph Foundations

Overview

Graphs are everywhere in competitive programming — grids, trees, networks, dependency chains. This chapter teaches you to see graph structure in problems and apply the right traversal or shortest-path algorithm. BFS and DFS are the backbone; Dijkstra and Bellman-Ford handle weighted paths; Kruskal builds minimum spanning trees. If a problem involves connections between things, you'll reach for something in this chapter.

Navigation

Coming from: Chapter 2 — Data Structures — segment trees, DSU, and the data structures that power efficient algorithms
Going to: Chapter 4 — Dynamic Programming — DP state design from 1D recurrences to bitmask and tree DP
Bridge: BRIDGE-to-dp.md — the link between graph structure and dynamic programming

Topics at a Glance

#	Topic	Difficulty	Key Trigger Phrase
01	Graph Representation	Beginner	"Store a graph" — adjacency list vs. matrix
02	BFS	Beginner	"Shortest path in unweighted graph"
03	DFS and Tree DFS	Beginner	"Visit all reachable nodes" or "cycle detection"
04	Bipartite Graphs	Intermediate	"Two-color the graph" or "split into two groups"
05	Topological Sort	Intermediate	"Ordering with prerequisites" (DAG)
06	DP on DAG	Intermediate	"Longest path in DAG" or "count paths"
07	Dijkstra's Algorithm	Intermediate	"Shortest path" + non-negative weights
08	Bellman-Ford	Intermediate	"Shortest path" + negative weights or "detect negative cycle"
09	Floyd-Warshall	Intermediate	"All-pairs shortest paths" with n ≤ 500
10	MST — Kruskal	Intermediate	"Minimum cost to connect all nodes"
11	MST — Prim	Intermediate	"MST on dense graphs"
12	Euler Path	Intermediate	"Traverse every edge exactly once"
13	Functional Graphs	Intermediate	"Each node has exactly one outgoing edge" (permutation cycles)
14	LCA with Binary Lifting	Intermediate	"Lowest common ancestor" or "distance on tree"

If You Only Read 3 Files

1. DFS and Tree DFS — because DFS is the foundation of almost every graph algorithm: cycle detection, connected components, topological sort, bridges, SCCs. If you only learn one traversal, make it DFS.
2. Dijkstra's Algorithm — because "shortest path" is one of the most common problem types on Codeforces, and Dijkstra with a priority queue is the standard tool from Div 2 C onward.
3. LCA with Binary Lifting — because tree path queries (distance, maximum edge, etc.) appear constantly, and binary lifting is the clean O(n log n) approach that extends to many related problems.

Cross-Chapter Connections

• BFS and DFS — not sure which to use? See the BFS vs DFS Guide in Chapter 11
• Topological Sort leads directly to DP on DAG here, and to the DP Thinking Framework in Chapter 4
• MST — Kruskal requires Union-Find (DSU) from Chapter 2
• LCA with Binary Lifting extends into Euler Tour and LCA in Chapter 6 for range-query-based LCA
• After mastering DFS here, advance to Bridges and Articulation Points and SCCs in Chapter 6

---

File Listing

File	Topic	Level
graph-representation	Graph Representation	⭐
bfs	Breadth-First Search	⭐
dfs-and-tree-dfs	DFS and Tree DFS	⭐
topological-sort	Topological Sort	⭐⭐
bipartite-graphs	Bipartite Graphs	⭐⭐
dijkstra	Dijkstra's Algorithm	⭐⭐
bellman-ford	Bellman-Ford Algorithm	⭐⭐
floyd-warshall	Floyd-Warshall Algorithm	⭐⭐
mst-kruskal	MST — Kruskal's Algorithm	⭐⭐
mst-prim	MST — Prim's Algorithm	⭐⭐
dp-on-dag	DP on DAG	⭐⭐
euler-path	Euler Path and Circuit	⭐⭐
functional-graphs	Functional Graphs	⭐⭐
lca-binary-lifting	LCA with Binary Lifting	⭐⭐

Suggested Reading Order

1. graph-representation — adjacency list, matrix, and edge list
2. bfs — level-by-level traversal and shortest paths in unweighted graphs
3. dfs-and-tree-dfs — depth-first traversal, the backbone of graph algorithms
4. topological-sort — linear ordering of DAG vertices
5. bipartite-graphs — two-coloring and matching foundations
6. dijkstra — shortest paths with non-negative weights
7. bellman-ford — shortest paths with negative weights
8. floyd-warshall — all-pairs shortest paths in O(n³)
9. mst-kruskal — minimum spanning tree via sorted edges + DSU
10. mst-prim — minimum spanning tree via greedy vertex growth
11. dp-on-dag — dynamic programming along topological order
12. euler-path — traverse every edge exactly once
13. functional-graphs — graphs with out-degree 1 and cycle detection
14. lca-binary-lifting — lowest common ancestor via sparse ancestor table