Graph Types & Representations
Directed vs Undirected
- Directed: Edge A→B ≠ B→A (dependencies, web pages)
- Undirected: Edge A-B means both A→B and B→A (roads, friends)
- Weighted: Edges have costs (GPS, network routing)
- DAG: Directed Acyclic Graph (topological sort)
Representations (choose wisely)
- Adjacency List: vector<vector<int>> — sparse graphs O(V+E)
- Adjacency Matrix: int[][] — dense graphs, O(1) edge lookup
- Edge List: vector<pair> — sorting-based algorithms (Kruskal)
- Most interview problems → adjacency list
C++
// Adjacency List — most common in interviews
int n = 5; // 5 nodes: 0,1,2,3,4
vector<vector<int>> adj(n);
// Add undirected edge 0-1
adj[0].push_back(1);
adj[1].push_back(0);
// Add directed edge 2→3
adj[2].push_back(3);
// Build from edge list input
vector<vector<int>> buildAdj(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]]); // omit for directed
}
return adj;
}
BFS & DFS Templates
C++
// BFS — shortest path in unweighted graph, level-by-level
void bfs(int start, vector<vector<int>>& adj, int n) {
vector<bool> visited(n, false);
queue<int> q;
q.push(start); visited[start] = true;
while (!q.empty()) {
int node = q.front(); q.pop();
// process node here
for (int nb : adj[node]) {
if (!visited[nb]) {
visited[nb] = true;
q.push(nb);
}
}
}
}
// DFS — connected components, cycle detection, backtracking
void dfs(int node, vector<vector<int>>& adj, vector<bool>& vis) {
vis[node] = true;
// process node here
for (int nb : adj[node]) {
if (!vis[nb]) dfs(nb, adj, vis);
}
}
// DFS on grid (4-directional)
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void dfsGrid(vector<vector<char>>& grid, int r, int c) {
int m=grid.size(), n=grid[0].size();
if (r<0||r>=m||c<0||c>=n||grid[r][c]!='1') return;
grid[r][c] = '0'; // mark visited
for (int d=0; d<4; d++) dfsGrid(grid, r+dx[d], c+dy[d]);
}
Union-Find (Disjoint Set Union)
Efficiently groups elements into sets and checks if two elements are in the same set. O(α(n)) ≈ O(1) amortized with path compression + union by rank.
C++
struct UnionFind {
vector<int> parent, rank;
int components;
UnionFind(int n) : parent(n), rank(n,0), components(n) {
iota(parent.begin(), parent.end(), 0); // parent[i]=i
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compress
return parent[x];
}
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false; // already connected
if (rank[a] < rank[b]) swap(a, b);
parent[b] = a;
if (rank[a] == rank[b]) rank[a]++;
components--;
return true;
}
bool connected(int a, int b) { return find(a)==find(b); }
};
// Use: UF uf(n); uf.unite(a,b); uf.connected(a,b);
// uf.components = number of disconnected sets
Interactive: BFS vs DFS
Select BFS or DFS to explore the same 7-node graph from node A. BFS uses a queue (frontier = purple, level-by-level). DFS uses a stack (dive deep first, backtrack). Notice how BFS finds shortest paths while DFS may take longer routes first.
Deeper Understanding
🧠 Under the Hood
Graphs are stored as adjacency lists for interview problems because most real graphs are sparse (E ≪ V²). An adjacency matrix wastes O(V²) memory storing zeros. Both representations give the same asymptotic BFS/DFS results, but list traversal is faster in practice for sparse graphs.
⚖️ When to Use / When NOT to Use
✅ Use BFS for shortest path (unweighted) or level-by-level exploration
BFS guarantees that the first time a node is reached, the path length is minimum (for uniform-cost edges). DFS cannot make this guarantee.
✅ Use DFS for connected components, cycle detection, topological sort, backtracking
DFS's implicit stack (or explicit stack) naturally models depth-first exploration — ideal when you need to enumerate all paths or check reachability.
✅ Use Union-Find for dynamic connectivity / number of components with frequent merges
Union-Find is O(α(n)) amortized per operation — faster than re-running BFS/DFS when the graph changes incrementally (add edges only).
❌ Avoid DFS for shortest path in unweighted graphs
Instead: Use BFS. DFS may find a long winding path before discovering the short direct one.
❌ Avoid adjacency matrix for sparse graphs (most interview problems)
Instead: Use adjacency list. Matrix uses O(V²) space regardless of edge count; list uses O(V+E).
🚫 Common Misconceptions
❌ "DFS finds shortest paths"
DFS explores depth-first — it may visit many long paths before finding the short one. Only BFS guarantees shortest path in unweighted graphs. For weighted, use Dijkstra (greedy) or Bellman-Ford (DP).
❌ "Mark visited after popping from queue/stack"
Mark visited before enqueuing (BFS) or recursing (DFS). Marking after pop causes the same node to be enqueued multiple times, leading to O(E) extra work or infinite loops on cycles.
❌ "Graphs are just harder trees"
Key difference: graphs can have cycles. A tree is a graph with exactly V-1 edges and no cycles. Cycle detection and the visited set are essential in graph algorithms but implicit in tree recursion.
🎤 Interview Follow-ups
How to detect if a graph is bipartite?
BFS/DFS with 2-coloring: assign alternating colors to adjacent nodes. If any edge connects same-colored nodes, graph is not bipartite. Grid-coloring (0-1 BFS) is a special case.
When to use Dijkstra vs BFS?
BFS for unweighted (all edge costs equal). Dijkstra for non-negative weighted graphs — it generalizes BFS using a priority queue instead of a simple queue, processing nearest node first.
Recursion depth limit for DFS on large graphs?
Recursive DFS can hit OS stack limits (~10⁵ frames on most systems). Convert to iterative DFS using an explicit stack when graph size is large or tree may be skewed.
Practice Problems
#200Number of IslandsMedium
Given a 2D grid of '1' (land) and '0' (water), count the number of islands.
Pattern: DFS flood-fill. For each unvisited '1', run DFS to mark the whole island '0'. Increment counter each time DFS starts.
C++
void dfs(vector<vector<char>>& g, int r, int c) {
int m=g.size(), n=g[0].size();
if (r<0||r>=m||c<0||c>=n||g[r][c]!='1') return;
g[r][c]='0';
dfs(g,r+1,c); dfs(g,r-1,c); dfs(g,r,c+1); dfs(g,r,c-1);
}
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int r=0; r<grid.size(); r++)
for (int c=0; c<grid[0].size(); c++)
if (grid[r][c]=='1') { dfs(grid,r,c); count++; }
return count;
}
// Time: O(m*n) Space: O(m*n) call stack
#133Clone GraphMedium
Deep copy a graph. Each node has a val and list of neighbors.
Pattern: DFS + HashMap. Map old node → cloned node. If already cloned, return from map. Else clone, recurse on neighbors.
C++
unordered_map<Node*, Node*> mp;
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
if (mp.count(node)) return mp[node];
Node* clone = new Node(node->val);
mp[node] = clone;
for (Node* nb : node->neighbors)
clone->neighbors.push_back(cloneGraph(nb));
return clone;
}
// Time: O(V+E) Space: O(V)
#207Course ScheduleMedium
Can you finish all courses given prerequisites? Detect cycle in directed graph.
Pattern: Topological sort (Kahn's BFS). Build in-degree map. Start with nodes having in-degree 0. Process BFS, decrement in-degrees. If all nodes processed, no cycle.
C++
bool canFinish(int n, vector<vector<int>>& prereqs) {
vector<vector<int>> adj(n);
vector<int> indegree(n, 0);
for (auto& p : prereqs) {
adj[p[1]].push_back(p[0]);
indegree[p[0]]++;
}
queue<int> q;
for (int i=0; i<n; i++) if (!indegree[i]) q.push(i);
int done = 0;
while (!q.empty()) {
int cur = q.front(); q.pop(); done++;
for (int nb : adj[cur])
if (--indegree[nb] == 0) q.push(nb);
}
return done == n;
}
// Time: O(V+E) Space: O(V+E)
#417Pacific Atlantic Water FlowMedium
Find cells from which water can flow to both the Pacific and Atlantic oceans. Water flows to equal or lower neighbors.
Pattern: Reverse BFS from ocean borders. Pacific can reach cells from top/left border. Atlantic from bottom/right. Answer = intersection.
C++
vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
int m=h.size(), n=h[0].size();
auto bfs = [&](vector<pair<int,int>> seeds) {
vector<vector<bool>> vis(m, vector<bool>(n,false));
queue<pair<int,int>> q;
for (auto s : seeds) { q.push(s); vis[s.first][s.second]=true; }
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
while (!q.empty()) {
auto [r,c] = q.front(); q.pop();
for (int d=0; d<4; d++) {
int nr=r+dx[d], nc=c+dy[d];
if (nr<0||nr>=m||nc<0||nc>=n||vis[nr][nc]||h[nr][nc]<h[r][c]) continue;
vis[nr][nc]=true; q.push({nr,nc});
}
}
return vis;
};
vector<pair<int,int>> pac, atl;
for (int i=0; i<m; i++) { pac.push_back({i,0}); atl.push_back({i,n-1}); }
for (int j=0; j<n; j++) { pac.push_back({0,j}); atl.push_back({m-1,j}); }
auto p=bfs(pac), a=bfs(atl);
vector<vector<int>> res;
for (int i=0;i<m;i++) for(int j=0;j<n;j++) if(p[i][j]&&a[i][j]) res.push_back({i,j});
return res;
}
// Time: O(m*n) Space: O(m*n)
#684Redundant ConnectionMedium
Find the edge that creates a cycle in an undirected graph. Return that edge.
Pattern: Union-Find. Process edges one by one. If two endpoints are already in the same set → this edge creates a cycle → return it.
C++
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
UnionFind uf(n+1);
for (auto& e : edges) {
if (!uf.unite(e[0], e[1])) return e; // unite returns false if same set
}
return {};
}
// Time: O(n α(n)) ≈ O(n) Space: O(n)
#994Rotting OrangesMedium
Grid of empty(0)/fresh(1)/rotten(2) oranges. Each minute, rotten spreads to adjacent fresh. Return minutes to rot all, or -1 if impossible.
Pattern: Multi-source BFS. Start BFS from ALL rotten oranges simultaneously. Level = time. After BFS, check if any fresh remain.
C++
int orangesRotting(vector<vector<int>>& grid) {
int m=grid.size(), n=grid[0].size(), fresh=0, mins=0;
queue<pair<int,int>> q;
for (int r=0;r<m;r++) for(int c=0;c<n;c++) {
if(grid[r][c]==2) q.push({r,c});
if(grid[r][c]==1) fresh++;
}
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
while (!q.empty() && fresh) {
mins++;
int sz=q.size();
while (sz--) {
auto[r,c]=q.front(); q.pop();
for(int d=0;d<4;d++){
int nr=r+dx[d],nc=c+dy[d];
if(nr<0||nr>=m||nc<0||nc>=n||grid[nr][nc]!=1) continue;
grid[nr][nc]=2; fresh--; q.push({nr,nc});
}
}
}
return fresh==0 ? mins : -1;
}
// Time: O(m*n) Space: O(m*n)
#127Word LadderHard
Transform beginWord to endWord one letter at a time (each intermediate must be in wordList). Find shortest transformation sequence length.
Pattern: BFS (shortest path in unweighted graph where edges = one letter apart). Use unordered_set for O(1) word lookup.
C++
int ladderLength(string begin, string end, vector<string>& wordList) {
unordered_set<string> wordSet(wordList.begin(), wordList.end());
if (!wordSet.count(end)) return 0;
queue<string> q; q.push(begin);
int steps = 1;
while (!q.empty()) {
int sz = q.size();
while (sz--) {
string word = q.front(); q.pop();
for (int i=0; i<word.size(); i++) {
string tmp = word;
for (char c='a'; c<='z'; c++) {
tmp[i] = c;
if (tmp == end) return steps+1;
if (wordSet.count(tmp)) { wordSet.erase(tmp); q.push(tmp); }
}
}
}
steps++;
}
return 0;
}
// Time: O(n * m * 26) Space: O(n)
#743Network Delay Time (Dijkstra)Medium
Weighted directed graph, signal sent from node k. Return time for all nodes to receive signal, or -1 if unreachable.
Pattern: Dijkstra's algorithm. Priority queue (min-heap) of (distance, node). Always process shortest known path first.
C++
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
vector<vector<pair<int,int>>> adj(n+1);
for (auto& t : times) adj[t[0]].push_back({t[1],t[2]});
vector<int> dist(n+1, INT_MAX);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq;
dist[k]=0; pq.push({0,k});
while (!pq.empty()) {
auto[d,u]=pq.top(); pq.pop();
if (d>dist[u]) continue;
for (auto[v,w]:adj[u])
if(dist[u]+w<dist[v]) { dist[v]=dist[u]+w; pq.push({dist[v],v}); }
}
int res = *max_element(dist.begin()+1,dist.end());
return res==INT_MAX ? -1 : res;
}
// Time: O((V+E) log V) Space: O(V+E)
Approach decision: BFS for shortest path / level-by-level. DFS for connected components / backtracking / cycle detect. Union-Find for dynamic connectivity / number of components.