Master graph traversal techniques including breadth-first search, depth-first search, topological sorting, and advanced algorithms like Dijkstra's. Learn to model complex problems as graphs and solve them efficiently with proven patterns.
Understanding how to represent graphs and traverse them efficiently is essential for solving graph problems. Learn adjacency lists, BFS/DFS templates, and when to use each approach.
Adjacency List (Dictionary): Preferred for sparse graphs. Maps node → list of neighbors.
// Adjacency list using Dictionary Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); // Build graph from edges foreach (var (u, v) in edges) { if (!graph.ContainsKey(u)) { graph[u] = new List<int>(); } graph[u].Add(v); }
Adjacency Matrix: Dense graphs, O(1) edge lookup. Use when checking specific edges matters.
// Adjacency matrix for dense graphs bool[][] adj = new bool[n][]; for (int i = 0; i < n; i++) { adj[i] = new bool[n]; } // Add edge u → v adj[u][v] = true;
Use BFS to find the shortest path in unweighted graphs or explore level by level. Guarantees shortest distance from source.
// BFS template public void BFS(int start) { Queue<int> q = new Queue<int>(); HashSet<int> visited = new HashSet<int>(); q.Enqueue(start); visited.Add(start); while (q.Count > 0) { int u = q.Dequeue(); // Process node u if (!graph.ContainsKey(u)) continue; foreach (int v in graph[u]) { if (!visited.Contains(v)) { visited.Add(v); q.Enqueue(v); } } } }
Use DFS to explore deeply, detect cycles, or find connected components. Can use recursion or explicit stack.
// DFS template (recursive) private void DFS(int u, HashSet<int> visited) { visited.Add(u); // Process node u if (!graph.ContainsKey(u)) return; foreach (int v in graph[u]) { if (!visited.Contains(v)) { DFS(v, visited); } } }
Use for DAGs (Directed Acyclic Graphs). Sort nodes so all edges point from left to right. Also detects cycles.
// Topological sort using Kahn's algorithm (BFS) public int[] TopologicalSort(int n, int[][] edges) { Dictionary<int, int> indegree = new Dictionary<int, int>(); Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); for (int i = 0; i < n; i++) { indegree[i] = 0; graph[i] = new List<int>(); } foreach (var edge in edges) { int u = edge[0], v = edge[1]; graph[u].Add(v); indegree[v]++; } Queue<int> q = new Queue<int>(); for (int i = 0; i < n; i++) { if (indegree[i] == 0) q.Enqueue(i); } List<int> result = new List<int>(); while (q.Count > 0) { int u = q.Dequeue(); result.Add(u); foreach (int v in graph[u]) { indegree[v]--; if (indegree[v] == 0) q.Enqueue(v); } } return result.Count == n ? result.ToArray() : new int[0]; }
Efficiently track connected components and merge sets. Path compression + union by rank → nearly O(1).
// Union-Find with path compression and union by rank class UnionFind { int[] parent, rank; public UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; rank[i] = 0; } } public int Find(int x) { if (parent[x] != x) { parent[x] = Find(parent[x]); // Path compression } return parent[x]; } public void Union(int x, int y) { int px = Find(x), py = Find(y); if (px == py) return; if (rank[px] < rank[py]) { parent[px] = py; } else if (rank[px] > rank[py]) { parent[py] = px; } else { parent[py] = px; rank[px]++; } } }
Find shortest path in graphs with non-negative weights. Use PriorityQueue for efficiency.
// Dijkstra's algorithm public int[] Dijkstra(int n, int[][] edges, int start) { int[] dist = new int[n]; Array.Fill(dist, int.MaxValue); dist[start] = 0; var pq = new PriorityQueue<(int, int), int>(); pq.Enqueue((dist[start], start), dist[start]); while (pq.Count > 0) { (_, int u) = pq.Dequeue(); foreach (var edge in edges) { if (edge[0] != u) continue; int v = edge[1], w = edge[2]; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.Enqueue((dist[v], v), dist[v]); } } } return dist; }
Find a person who is trusted by everyone and trusts no one. Use indegree/outdegree analysis.
In a town of n people labeled from 1 to n, find the judge. A judge trusts nobody and is trusted by everyone. Given array of [a, b] meaning a trusts b, return the judge's label or -1 if no judge exists.
public int FindJudge(int n, int[][] trust) { int[] trustCount = new int[n + 1]; int[] trustByCount = new int[n + 1]; foreach (var edge in trust) { int a = edge[0], b = edge[1]; trustCount[a]++; // a trusts b trustByCount[b]++; // b is trusted by a } for (int i = 1; i <= n; i++) { if (trustCount[i] == 0 && trustByCount[i] == n - 1) { return i; } } return -1; }
Input: n = 3, trust = [[1,3], [2,3]]
trustCount: [0, 1, 1, 0] (person 1 trusts 1, person 2 trusts 1, person 3 trusts 0)
trustByCount: [0, 0, 0, 2] (person 3 is trusted by 2 people)
Output: 3 ✓
Basic BFS/DFS to check if path exists between two nodes.
Given undirected graph as edge list, return true if path exists from source to destination.
Use BFS to explore from source. If we reach destination, path exists.
public bool ValidPath(int n, int[][] edges, int source, int destination) { if (source == destination) return true; Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); for (int i = 0; i < n; i++) { graph[i] = new List<int>(); } foreach (var edge in edges) { int u = edge[0], v = edge[1]; graph[u].Add(v); graph[v].Add(u); // Undirected } Queue<int> q = new Queue<int>(); HashSet<int> visited = new HashSet<int>(); q.Enqueue(source); visited.Add(source); while (q.Count > 0) { int u = q.Dequeue(); if (u == destination) return true; foreach (int v in graph[u]) { if (!visited.Contains(v)) { visited.Add(v); q.Enqueue(v); } } } return false; }
Count connected components of land in a grid using DFS/BFS flood fill.
Given m×n grid with 1s (land) and 0s (water), count number of islands. Island is connected horizontally or vertically.
Iterate through grid. When finding unvisited land (1), do BFS/DFS to mark entire island, increment counter.
public int NumIslands(char[][] grid) { int m = grid.Length, n = grid[0].Length; int count = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '1') { BFS(grid, i, j, m, n); count++; } } } return count; } private void BFS(char[][] grid, int si, int sj, int m, int n) { Queue<(int, int)> q = new Queue<(int, int)>(); q.Enqueue((si, sj)); grid[si][sj] = '0'; // Mark visited int[][] dirs = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} }; while (q.Count > 0) { (var i, var j) = q.Dequeue(); foreach (var dir in dirs) { int ni = i + dir[0], nj = j + dir[1]; if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == '1') { grid[ni][nj] = '0'; q.Enqueue((ni, nj)); } } } }
Deep copy a graph using BFS and HashMap for reference mapping.
Given a graph node, return a deep copy of the entire graph. Include all nodes and edges.
Use BFS with HashMap to track old → new node mappings. Create new nodes, then connect neighbors.
public Node CloneGraph(Node node) { if (node == null) return null; Dictionary<Node, Node> map = new Dictionary<Node, Node>(); Queue<Node> q = new Queue<Node>(); q.Enqueue(node); map[node] = new Node(node.val); while (q.Count > 0) { Node curr = q.Dequeue(); foreach (Node neighbor in curr.neighbors) { if (!map.ContainsKey(neighbor)) { map[neighbor] = new Node(neighbor.val); q.Enqueue(neighbor); } map[curr].neighbors.Add(map[neighbor]); } } return map[node]; }
HashMap prevents revisiting nodes and maintains reference equality. When we encounter a neighbor, if it's not in map, create it; otherwise reuse existing copy.
Detect cycle in directed graph using topological sort (Kahn's algorithm).
Given n courses and prerequisites [a,b] meaning must take b before a, determine if can finish all courses (no cycle).
Use Kahn's algorithm. Count indegrees, enqueue nodes with indegree 0, process and decrement neighbors. If processed all nodes, no cycle.
public bool CanFinish(int numCourses, int[][] prerequisites) { int[] indegree = new int[numCourses]; Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); for (int i = 0; i < numCourses; i++) { graph[i] = new List<int>(); } foreach (var pre in prerequisites) { graph[pre[1]].Add(pre[0]); indegree[pre[0]]++; } Queue<int> q = new Queue<int>(); for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) q.Enqueue(i); } int count = 0; while (q.Count > 0) { int u = q.Dequeue(); count++; foreach (int v in graph[u]) { indegree[v]--; if (indegree[v] == 0) q.Enqueue(v); } } return count == numCourses; }
Topological ordering exists IFF graph is acyclic. If we can't process all nodes, there's a cycle.
Return the topological ordering of courses (or empty if cycle exists).
Return a valid ordering to take all courses, or empty array if impossible (cycle exists).
Same as Course Schedule, but collect nodes in topological order into result list instead of just counting.
public int[] FindOrder(int numCourses, int[][] prerequisites) { int[] indegree = new int[numCourses]; Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>(); for (int i = 0; i < numCourses; i++) { graph[i] = new List<int>(); } foreach (var pre in prerequisites) { graph[pre[1]].Add(pre[0]); indegree[pre[0]]++; } Queue<int> q = new Queue<int>(); for (int i = 0; i < numCourses; i++) { if (indegree[i] == 0) q.Enqueue(i); } List<int> result = new List<int>(); while (q.Count > 0) { int u = q.Dequeue(); result.Add(u); foreach (int v in graph[u]) { indegree[v]--; if (indegree[v] == 0) q.Enqueue(v); } } return result.Count == numCourses ? result.ToArray() : new int[0]; }
Find cheapest path with at most K edges using modified Bellman-Ford / BFS.
Find cheapest flight from src to dst with at most K stops (edges). Return minimum cost or -1 if impossible.
Use Bellman-Ford variant. For each of K+1 iterations, relax all edges. Track best distance per node.
public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int K) { int[] dist = new int[n]; Array.Fill(dist, int.MaxValue); dist[src] = 0; // Relax edges K+1 times for (int i = 0; i <= K; i++) { int[] newDist = (int[])dist.Clone(); foreach (var flight in flights) { int u = flight[0], v = flight[1], w = flight[2]; if (dist[u] != int.MaxValue && dist[u] + w < newDist[v]) { newDist[v] = dist[u] + w; } } dist = newDist; } return dist[dst] == int.MaxValue ? -1 : dist[dst]; }
By iterating K+1 times, we ensure we consider paths with at most K edges. Bellman-Ford naturally handles this constraint.
Find time for signal to reach all nodes from source using Dijkstra's algorithm.
Signal sent from node K. Time to travel u → v is w. Find time for signal to reach all nodes.
Use Dijkstra's algorithm. Find shortest path from K to all nodes. Return maximum distance (last node reached).
public int NetworkDelayTime(int[][] times, int n, int k) { Dictionary<int, List<(int, int)>> graph = new Dictionary<int, List<(int, int)>>(); for (int i = 1; i <= n; i++) { graph[i] = new List<(int, int)>(); } foreach (var edge in times) { graph[edge[0]].Add((edge[1], edge[2])); } int[] dist = new int[n + 1]; Array.Fill(dist, int.MaxValue); dist[k] = 0; var pq = new PriorityQueue<(int, int), int>(); pq.Enqueue((dist[k], k), dist[k]); while (pq.Count > 0) { (_, int u) = pq.Dequeue(); if (dist[u] == int.MaxValue) continue; foreach (var (v, w) in graph[u]) { if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.Enqueue((dist[v], v), dist[v]); } } } int maxDist = 0; for (int i = 1; i <= n; i++) { if (dist[i] == int.MaxValue) return -1; maxDist = Math.Max(maxDist, dist[i]); } return maxDist; }
Find cells where water flows to both oceans using reverse BFS from borders.
Given m×n grid of elevations, find cells where water flows to both Pacific (top-left) and Atlantic (bottom-right) oceans. Water flows downhill or on same level.
Key insight: Reverse the problem. Start from ocean borders and flow uphill (reverse direction). Cell reaches both oceans if visited from both directions.
public IList<IList<int>> PacificAtlantic(int[][] heights) { int m = heights.Length, n = heights[0].Length; bool[][] pacific = new bool[m][], atlantic = new bool[m][]; for (int i = 0; i < m; i++) { pacific[i] = new bool[n]; atlantic[i] = new bool[n]; } // BFS from Pacific border (top, left) BFS(heights, pacific, 0, 0, m, n); // BFS from Atlantic border (bottom, right) BFS(heights, atlantic, m - 1, n - 1, m, n); List<IList<int>> result = new List<IList<int>>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (pacific[i][j] && atlantic[i][j]) { result.Add(new List<int> { i, j }); } } } return result; } private void BFS(int[][] heights, bool[][] visited, int si, int sj, int m, int n) { Queue<(int, int)> q = new Queue<(int, int)>(); q.Enqueue((si, sj)); visited[si][sj] = true; int[][] dirs = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} }; while (q.Count > 0) { (var i, var j) = q.Dequeue(); foreach (var dir in dirs) { int ni = i + dir[0], nj = j + dir[1]; if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj] && heights[ni][nj] >= heights[i][j]) { visited[ni][nj] = true; q.Enqueue((ni, nj)); } } } }
Instead of checking if each cell flows downhill to oceans (hard), reverse it: from oceans, flow uphill. If cell can be reached from both oceans, it's valid.
Multi-source BFS to spread rot and find time to rot all oranges.
Grid with 0 (empty), 1 (fresh orange), 2 (rotten orange). Rotten spreads to adjacent fresh each minute. Return minutes to rot all, or -1 if impossible.
Multi-source BFS: enqueue all rotten oranges initially, spread rot level by level, track time.
public int OrangesRotting(int[][] grid) { int m = grid.Length, n = grid[0].Length; Queue<(int, int)> q = new Queue<(int, int)>(); int freshCount = 0; // Enqueue all rotten oranges initially for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 2) q.Enqueue((i, j)); else if (grid[i][j] == 1) freshCount++; } } int[][] dirs = new int[][] { new int[] {0, 1}, new int[] {1, 0}, new int[] {0, -1}, new int[] {-1, 0} }; int time = 0; while (q.Count > 0 && freshCount > 0) { int qSize = q.Count; for (int i = 0; i < qSize; i++) { (var r, var c) = q.Dequeue(); foreach (var dir in dirs) { int nr = r + dir[0], nc = c + dir[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) { grid[nr][nc] = 2; q.Enqueue((nr, nc)); freshCount--; } } } if (freshCount > 0) time++; } return freshCount == 0 ? time : -1; }
Multi-source BFS: all rotten oranges spread simultaneously, like concentric circles expanding. Track fresh count to detect if all rotten.
Find 'O' regions completely surrounded by 'X' using border DFS.
Given m×n board with 'X' and 'O', capture all 'O' regions surrounded by 'X'. 'O' connected to border cannot be captured.
Key insight: Reverse logic. Mark all 'O' connected to border as safe. Then flip remaining 'O' to 'X'.
public void Solve(char[][] board) { int m = board.Length, n = board[0].Length; // DFS from all border 'O's for (int i = 0; i < m; i++) { DFS(board, i, 0, m, n); DFS(board, i, n - 1, m, n); } for (int j = 0; j < n; j++) { DFS(board, 0, j, m, n); DFS(board, m - 1, j, m, n); } // Flip remaining O's to X's for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (board[i][j] == 'O') board[i][j] = 'X'; else if (board[i][j] == '*') board[i][j] = 'O'; } } } private void DFS(char[][] board, int i, int j, int m, int n) { if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return; board[i][j] = '*'; // Mark as safe temporarily DFS(board, i + 1, j, m, n); DFS(board, i - 1, j, m, n); DFS(board, i, j + 1, m, n); DFS(board, i, j - 1, m, n); }
Mark all 'O' reachable from border as '#' (safe), then flip remaining 'O' to 'X', finally restore marked cells.
Find shortest transformation path between words using BFS.
Find shortest path from beginWord to endWord, changing one letter at a time. All intermediate words must be in wordList.
Use BFS. For each word, generate all neighbors (change one letter). Find shortest path to endWord.
public int LadderLength(string beginWord, string endWord, IList<string> wordList) { HashSet<string> words = new HashSet<string>(wordList); if (!words.Contains(endWord)) return 0; Queue<string> q = new Queue<string>(); HashSet<string> visited = new HashSet<string>(); q.Enqueue(beginWord); visited.Add(beginWord); int level = 1; while (q.Count > 0) { int size = q.Count; for (int i = 0; i < size; i++) { string word = q.Dequeue(); if (word == endWord) return level; // Generate neighbors foreach (string neighbor in GetNeighbors(word, words)) { if (!visited.Contains(neighbor)) { visited.Add(neighbor); q.Enqueue(neighbor); } } } level++; } return 0; } private List<string> GetNeighbors(string word, HashSet<string> words) { List<string> neighbors = new List<string>(); char[] chars = word.ToCharArray(); for (int i = 0; i < chars.Length; i++) { char old = chars[i]; for (char c = 'a'; c <= 'z'; c++) { if (c == old) continue; chars[i] = c; string newWord = new string(chars); if (words.Contains(newWord)) neighbors.Add(newWord); } chars[i] = old; } return neighbors; }
For each word (N words), try L positions, try 26 letters, check if in set. O(N * L * 26 * log N) ~= O(N * L^2).
Count connected components using Union-Find.
Given n nodes and edges, count number of connected components.
Use Union-Find. Union nodes in each edge, count distinct roots at end.
public int CountComponents(int n, int[][] edges) { UnionFind uf = new UnionFind(n); foreach (var edge in edges) { uf.Union(edge[0], edge[1]); } HashSet<int> roots = new HashSet<int>(); for (int i = 0; i < n; i++) { roots.Add(uf.Find(i)); } return roots.Count; } class UnionFind { int[] parent, rank; public UnionFind(int n) { parent = new int[n]; rank = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; } public int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; } public void Union(int x, int y) { int px = Find(x), py = Find(y); if (px == py) return; if (rank[px] < rank[py]) parent[px] = py; else if (rank[px] > rank[py]) parent[py] = px; else { parent[py] = px; rank[px]++; } } }
Check if graph is a valid tree: n-1 edges and connected.
Given n nodes and edges, check if graph is a valid tree. Tree: connected + n-1 edges + no cycles.
Key insight: Valid tree has exactly n-1 edges and is connected. Use Union-Find to detect cycles.
public bool ValidTree(int n, int[][] edges) { // Tree must have exactly n-1 edges if (edges.Length != n - 1) return false; UnionFind uf = new UnionFind(n); foreach (var edge in edges) { int x = edge[0], y = edge[1]; // Cycle detected if (uf.Find(x) == uf.Find(y)) return false; uf.Union(x, y); } // Check if all nodes are in one component int root = uf.Find(0); for (int i = 1; i < n; i++) { if (uf.Find(i) != root) return false; } return true; }
Three conditions for valid tree: (1) n-1 edges, (2) no cycles (Union-Find), (3) connected (all same root).
Determine ordering of characters from sorted words using topological sort.
Given sorted list of words in alien language, return order of characters. If invalid, return empty string.
Compare adjacent words to find character ordering constraints. Build directed graph, topologically sort to get character order.
public string AlienOrder(string[] words) { Dictionary<char, int> indegree = new Dictionary<char, int>(); Dictionary<char, List<char>> graph = new Dictionary<char, List<char>>(); // Initialize all characters foreach (string word in words) { foreach (char c in word) { if (!indegree.ContainsKey(c)) { indegree[c] = 0; graph[c] = new List<char>(); } } } // Build graph from adjacent words for (int i = 0; i < words.Length - 1; i++) { string w1 = words[i], w2 = words[i + 1]; int minLen = Math.Min(w1.Length, w2.Length); if (w1.Length > w2.Length && minLen == w2.Length) return ""; for (int j = 0; j < minLen; j++) { char c1 = w1[j], c2 = w2[j]; if (c1 != c2) { if (!graph[c1].Contains(c2)) { graph[c1].Add(c2); indegree[c2]++; } break; } } } // Topological sort Queue<char> q = new Queue<char>(); foreach (var kvp in indegree) { if (kvp.Value == 0) q.Enqueue(kvp.Key); } StringBuilder result = new StringBuilder(); while (q.Count > 0) { char u = q.Dequeue(); result.Append(u); foreach (char v in graph[u]) { indegree[v]--; if (indegree[v] == 0) q.Enqueue(v); } } return result.Length == indegree.Count ? result.ToString() : ""; }
Comparing adjacent words reveals ordering constraints. First differing character tells us relative order. Topological sort produces valid character ordering.