Graph
Graph Fundamentals
Vertices connected by edges โ the most general data structure for modeling relationships. Graphs power social networks, GPS navigation, dependency resolution, and every "shortest path" or "connected components" interview problem.
Foundations ยท Array ยท Linked List ยท Stack ยท Queue ยท HashMap ยท Binary Tree ยท BST ยท Heap ยท Trie ยท Graph ยท Sorting ยท Binary Search ยท Two Pointers ยท Sliding Window ยท Dynamic Prog.
01
Section One ยท Foundation
What is a Graph?
A graph is a collection of vertices (nodes) connected by edges โ unlike trees, there's no root, no parent-child hierarchy, and edges can form cycles. A graph can be directed (edges have a direction, like Twitter follows) or undirected (edges are bidirectional, like Facebook friendships). It can be weighted (each edge carries a cost, like road distances) or unweighted. The two dominant storage formats are an adjacency list (each vertex stores a list of neighbors โ space-efficient for sparse graphs) and an adjacency matrix (a 2D boolean/weight array โ fast edge lookup but O(Vยฒ) space). Graphs are everywhere: social networks, web page links, dependency trees in build systems, flight routes, and the Internet itself. In Java, there's no built-in Graph class โ you build one from Map<Integer, List<Integer>> or a 2D array.
Analogy: Think of a city's metro system. Each station is a vertex, each rail connection between two stations is an edge, and the travel time between stations is the edge weight. Some lines are one-way (directed), most are bidirectional (undirected). Finding the fastest route from station A to station B is the shortest-path problem โ exactly what BFS and Dijkstra solve. If you need to check whether every station is reachable from any other station, that's the connected-components problem. The metro map IS a graph.
02
Section Two ยท Mental Model
How It Thinks
No root or hierarchy โ any vertex can connect to any other vertex
โถ
Cycles are possible โ every traversal must track visited nodes or it loops forever
Adjacency list stores only existing edges (Map<V, List<V>>)
โถ
O(V + E) space โ efficient for sparse graphs where E << Vยฒ, which covers most real-world cases
Adjacency matrix stores all possible edges in a VรV grid
โถ
O(1) edge lookup but O(Vยฒ) space โ only practical when the graph is dense or V is small
BFS explores neighbors level by level using a queue
โถ
Finds shortest path in unweighted graphs โ the first time BFS reaches a node, that's the minimum-edge path
DFS explores as deep as possible before backtracking using a stack (or recursion)
โถ
Detects cycles, finds connected components, and enables topological sort โ the backbone of dependency resolution
Directed edges impose order (AโB does not imply BโA)
โถ
Enables DAGs (directed acyclic graphs) โ the foundation for topological sort, build systems, and course scheduling
03
Section Three ยท Operations
Core Operations
Add Vertex & Edge
Insert a new vertex into the graph and connect it to existing vertices by adding edges to the adjacency list.
Pseudocode
function addVertex(graph, v):
if v not in graph:
graph[v] = [] // empty neighbor list // O(1) function addEdge(graph, u, v):
graph[u].add(v) // u โ v
graph[v].add(u) // v โ u (omit for directed) // O(1)
Add Edge โ connecting vertex D to vertex A in an undirected graph
Undirected = two directed entries:
- For undirected graphs, every
addEdge(u, v)adds v to u's list AND u to v's list. - Forgetting one direction is the #1 graph construction bug โ BFS/DFS will miss paths because the edge only works one way.
BFS (Breadth-First Search)
Explore all neighbors at the current depth before moving deeper โ guarantees shortest path (minimum edges) in unweighted graphs.
Pseudocode
function bfs(graph, start):
visited = {start}
queue = [start]
while queue is not empty:
node = queue.dequeue()
process(node)
for each neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.enqueue(neighbor) // O(V + E)
BFS โ level-by-level exploration from vertex A
Mark visited BEFORE enqueueing:
- Add a node to
visitedwhen you enqueue it, not when you dequeue it. - If you wait until dequeue, multiple neighbors can enqueue the same node simultaneously, causing duplicate processing and incorrect shortest-path distances.
DFS (Depth-First Search)
Explore as far as possible along each branch before backtracking โ the foundation for cycle detection, topological sort, and connected components.
Pseudocode
function dfs(graph, node, visited):
visited.add(node)
process(node)
for each neighbor in graph[node]:
if neighbor not in visited:
dfs(graph, neighbor, visited) // O(V + E)
DFS โ depth-first exploration from vertex A
Iterative DFS with explicit stack:
- For deep graphs, recursion can cause
StackOverflowError. - Replace the call stack with an explicit
Deque<Integer>โ push neighbors, pop next node. - The iterative version handles graphs with thousands of nodes that recursive DFS cannot.
Common Mistake: Forgetting the
visited set in graphs with cycles. In a tree, DFS/BFS naturally terminates because there are no cycles. In a graph, revisiting a node means infinite recursion (DFS) or infinite loop (BFS). Always initialize a visited set before traversal โ this is the single most common graph bug.
04
Section Four ยท Implementation
Build It Once
Build this from scratch once โ it makes the mechanics concrete. In any real project or interview, reach for the built-in (Section 05).
Java โ Graph core mechanics (adjacency list)
class Graph {
private Map<Integer, List<Integer>> adj = new HashMap<>();
// ADD EDGE โ O(1) void addEdge(int u, int v) {
adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
// BFS โ O(V + E) List<Integer> bfs(int start) {
List<Integer> order = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int neighbor : adj.getOrDefault(node, List.of())) {
if (visited.add(neighbor)) // add returns false if already present
queue.add(neighbor);
}
}
return order;
}
// DFS โ O(V + E) void dfs(int node, Set<Integer> visited, List<Integer> order) {
visited.add(node);
order.add(node);
for (int neighbor : adj.getOrDefault(node, List.of())) {
if (!visited.contains(neighbor))
dfs(neighbor, visited, order);
}
}
}
Graph โ Full Implementation
Java โ Complete Graph implementation
import java.util.*;
public class Graph {
private Map<Integer, List<Integer>> adj = new HashMap<>();
// โโ Add vertex โโโโโโโโโโโโโโโโโโโโโโโโโโโโโ O(1) public void addVertex(int v) {
adj.putIfAbsent(v, new ArrayList<>());
}
// โโ Add edge (undirected) โโโโโโโโโโโโโโโโโโโ O(1) public void addEdge(int u, int v) {
adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
adj.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
// โโ Add directed edge โโโโโโโโโโโโโโโโโโโโโโโ O(1) public void addDirectedEdge(int u, int v) {
adj.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
}
// โโ BFS โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ O(V + E) public List<Integer> bfs(int start) {
List<Integer> order = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.add(start);
while (!queue.isEmpty()) {
int node = queue.poll();
order.add(node);
for (int nei : adj.getOrDefault(node, List.of())) {
if (visited.add(nei))
queue.add(nei);
}
}
return order;
}
// โโ DFS (recursive) โโโโโโโโโโโโโโโโโโโโโโโ O(V + E) public List<Integer> dfs(int start) {
List<Integer> order = new ArrayList<>();
dfsHelper(start, new HashSet<>(), order);
return order;
}
private void dfsHelper(int node, Set<Integer> visited, List<Integer> order) {
visited.add(node);
order.add(node);
for (int nei : adj.getOrDefault(node, List.of())) {
if (!visited.contains(nei))
dfsHelper(nei, visited, order);
}
}
// โโ Has path (BFS-based) โโโโโโโโโโโโโโโโโโ O(V + E) public boolean hasPath(int src, int dst) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(src);
queue.add(src);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == dst) return true;
for (int nei : adj.getOrDefault(node, List.of())) {
if (visited.add(nei))
queue.add(nei);
}
}
return false;
}
// โโ Connected components โโโโโโโโโโโโโโโโโโ O(V + E) public int countComponents() {
Set<Integer> visited = new HashSet<>();
int count = 0;
for (int vertex : adj.keySet()) {
if (!visited.contains(vertex)) {
dfsHelper(vertex, visited, new ArrayList<>());
count++;
}
}
return count;
}
// โโ Cycle detection (undirected) โโโโโโโโโโโ O(V + E) public boolean hasCycle() {
Set<Integer> visited = new HashSet<>();
for (int vertex : adj.keySet()) {
if (!visited.contains(vertex))
if (hasCycleDFS(vertex, -1, visited)) return true;
}
return false;
}
private boolean hasCycleDFS(int node, int parent, Set<Integer> visited) {
visited.add(node);
for (int nei : adj.getOrDefault(node, List.of())) {
if (!visited.contains(nei)) {
if (hasCycleDFS(nei, node, visited)) return true;
} else if (nei != parent) {
return true; // visited + not parent = cycle
}
}
return false;
}
// โโ Shortest path (unweighted BFS) โโโโโโโโ O(V + E) public int shortestPath(int src, int dst) {
Map<Integer, Integer> dist = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
dist.put(src, 0);
queue.add(src);
while (!queue.isEmpty()) {
int node = queue.poll();
if (node == dst) return dist.get(dst);
for (int nei : adj.getOrDefault(node, List.of())) {
if (!dist.containsKey(nei)) {
dist.put(nei, dist.get(node) + 1);
queue.add(nei);
}
}
}
return -1; // no path
}
@Override public String toString() {
StringBuilder sb = new StringBuilder();
for (var entry : adj.entrySet())
sb.append(entry.getKey()).append(" โ ").append(entry.getValue()).append("\n");
return sb.toString();
}
// โโ Main โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ public static void main(String[] args) {
Graph g = new Graph();
// 1. Build graph: 0-1-2-3-4, 1-4
g.addEdge(0, 1);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(1, 4);
System.out.println(g);
// 2. BFS from 0 System.out.println("BFS: " + g.bfs(0));
// โ [0, 1, 2, 4, 3] // 3. DFS from 0 System.out.println("DFS: " + g.dfs(0));
// โ [0, 1, 2, 3, 4] // 4. Shortest path System.out.println("Shortest 0โ4: " + g.shortestPath(0, 4));
// โ 2 (0โ1โ4) // 5. Cycle detection System.out.println("Has cycle: " + g.hasCycle());
// โ true (1-2-3-4-1)
}
}
Python โ Graph implementation
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.adj = defaultdict(list)
# โโ Add edge (undirected) โโโโโโโโโโโโโ O(1) def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u)
# โโ BFS โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ O(V + E) def bfs(self, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for nei in self.adj[node]:
if nei not in visited:
visited.add(nei)
queue.append(nei)
return order
# โโ DFS (recursive) โโโโโโโโโโโโโโโโโโโ O(V + E) def dfs(self, start):
visited = set()
order = []
self._dfs(start, visited, order)
return order
def _dfs(self, node, visited, order):
visited.add(node)
order.append(node)
for nei in self.adj[node]:
if nei not in visited:
self._dfs(nei, visited, order)
# โโ Has path โโโโโโโโโโโโโโโโโโโโโโโโโโ O(V + E) def has_path(self, src, dst):
visited = {src}
queue = deque([src])
while queue:
node = queue.popleft()
if node == dst:
return True for nei in self.adj[node]:
if nei not in visited:
visited.add(nei)
queue.append(nei)
return False # โโ Connected components โโโโโโโโโโโโโโ O(V + E) def count_components(self):
visited = set()
count = 0
for v in self.adj:
if v not in visited:
self._dfs(v, visited, [])
count += 1
return count
# โโ Cycle detection (undirected) โโโโโโ O(V + E) def has_cycle(self):
visited = set()
for v in self.adj:
if v not in visited:
if self._cycle_dfs(v, -1, visited):
return True return False def _cycle_dfs(self, node, parent, visited):
visited.add(node)
for nei in self.adj[node]:
if nei not in visited:
if self._cycle_dfs(nei, node, visited):
return True elif nei != parent:
return True return False # โโ Shortest path (unweighted BFS) โโโโ O(V + E) def shortest_path(self, src, dst):
dist = {src: 0}
queue = deque([src])
while queue:
node = queue.popleft()
if node == dst:
return dist[dst]
for nei in self.adj[node]:
if nei not in dist:
dist[nei] = dist[node] + 1
queue.append(nei)
return -1
# โโ Demo โโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโโ
g = Graph()
for u, v in [(0,1),(1,2),(2,3),(3,4),(1,4)]:
g.add_edge(u, v)
print("BFS:", g.bfs(0)) # [0, 1, 2, 4, 3]
print("DFS:", g.dfs(0)) # [0, 1, 2, 3, 4]
print("Shortest 0โ4:", g.shortest_path(0, 4)) # 2
print("Has cycle:", g.has_cycle()) # True
05
Section Five ยท Java Built-in
Use It In Java
IN JAVA โ No built-in Graph; build from Map + List
Use
Map<Integer, List<Integer>> (adjacency list) or int[][] (adjacency matrix) Import
import java.util.*; | Pattern | Complexity | Note |
|---|---|---|
map.computeIfAbsent(u, k -> new ArrayList<>()).add(v) | O(1) | Add edge โ creates list if vertex is new |
map.getOrDefault(u, List.of()) | O(1) | Get neighbors โ avoids null check |
new LinkedList<>() + poll() | O(1) | Queue for BFS โ use ArrayDeque for better perf |
new HashSet<>() + add() | O(1) | Visited set โ add() returns false if duplicate |
boolean[][] matrix | O(1) lookup | Adjacency matrix โ when V โค ~1000 |
int[][] edges | O(E) | Edge list input โ convert to adj list first |
int[] parent (Union-Find) | O(ฮฑ(n)) | Connected components without BFS/DFS |
โ Gotcha: LeetCode graph problems often give edges as
int[][] edges (edge list), not an adjacency list. Always convert to Map<Integer, List<Integer>> first โ iterating an edge list per query is O(E) per call, while an adjacency list gives O(degree) per call. The conversion loop is 3 lines; skipping it makes BFS/DFS O(VยทE) instead of O(V+E).
Choose Use
Map<Integer, List<Integer>> for sparse graphs (most interview problems). Use boolean[][] adjacency matrix only when V is small (< 1000) and you need O(1) edge existence checks โ like Floyd-Warshall or dense graph problems. 06
Section Six ยท Decision Guide
Pick The Right Structure
Decision Flowchart
Comparison Table
| Representation | Edge Lookup | Add Edge | Space | Best For |
|---|---|---|---|---|
| Adjacency List โ this | O(degree) | O(1) | O(V + E) | Sparse graphs, most interview problems |
| Adjacency Matrix | O(1) | O(1) | O(Vยฒ) | Dense graphs, Floyd-Warshall |
| Edge List | O(E) | O(1) | O(E) | Kruskal's MST, input format only |
| Union-Find | O(ฮฑ(n)) | O(ฮฑ(n)) | O(V) | Dynamic connectivity, MST |
07
Section Seven ยท Practice
Problems To Solve
Graph interview problems cluster around three patterns: BFS for shortest-path and level-order problems, DFS for connectivity and cycle detection, and topological sort for dependency ordering. Most medium-difficulty graph problems reduce to "build an adjacency list, then BFS or DFS" โ the hard part is recognizing that the problem is a graph problem and correctly modeling the vertices and edges.
| Difficulty | Pattern | Problem | Key Insight |
|---|---|---|---|
| Medium | bfs | Number of Islands โ LC 200 | Treat each '1' cell as a vertex with edges to adjacent '1' cells. BFS/DFS from each unvisited '1' marks an entire island โ count how many times you start a new traversal. |
| Medium | bfs | Rotting Oranges โ LC 994 | Multi-source BFS: enqueue all rotten oranges at once (level 0), then BFS spreads rot level by level. The answer is the number of BFS levels โ each level is one minute. |
| Medium | dfs | Clone Graph โ LC 133 | DFS with a HashMap mapping old node โ new node. When you visit a neighbor, check the map: if it exists, reuse it; if not, create it and recurse. The map prevents infinite loops on cycles. |
| Medium | dfs | Course Schedule โ LC 207 | Model courses as vertices, prerequisites as directed edges. Cycle in a directed graph = impossible to finish all courses. Use DFS with three states (unvisited, in-progress, done) to detect back edges. |
| Medium | bfs | 01 Matrix โ LC 542 | Multi-source BFS from all '0' cells simultaneously. Each level increments distance by 1. Initialize the queue with all zeros, mark all ones as unvisited โ BFS fills in the correct distances layer by layer. |
| Hard | bfs | Word Ladder โ LC 127 | Each word is a vertex; edges connect words differing by one character. BFS from beginWord finds shortest transformation sequence. The trick: generate all possible one-character mutations instead of comparing every pair of words. |
Interview Pattern:
- BFS and DFS each solve 40% of graph problems.
- If the problem asks for shortest path, minimum steps, or nearest distance โ use BFS.
- If it asks for "can you reach", cycle detection, connected components, or topological order โ use DFS.
- The remaining 20% require Dijkstra (weighted shortest path) or Union-Find (dynamic connectivity).
- Build the adjacency list first; the traversal is boilerplate.