Advanced Graph Topics¶
Table of Contents
1. Shortest Paths¶
Sample implementation
Single source shortest path
1# find the shortest path from k to all the nodes in the graph and then return the max 2def relax(dist, u, v, w): 3 if dist[v] > dist[u] + w: 4 dist[v] = dist[u] + w 5 return True 6 return False 7 8def bellman(): 9 dist = [inf] * (n + 1) 10 dist[k] = 0 11 # iterate as many times as there are number of edges 12 for _ in range(n-1): 13 # in every iteration, pick the minimum edge, relax the incident node 14 for u, v, w in sorted(times, key=lambda x:x[2]): 15 relax(dist, u, v, w) 16 max_dist = max(dist[1:]) 17 return max_dist if max_dist < inf else -1 18 19def build(n, times): 20 adj = [[] for _ in range(n + 1)] 21 for u, v, w in times: 22 adj[u].append((v, w)) 23 return adj 24 25def dijkstra(): 26 dist = [inf] * (n + 1) 27 dist[k] = 0 28 29 adj = build(n, times) 30 # we explore each vertex 31 # minheap should be ordered based on distance 32 # in every iteration, we take the tail vertex which has the minimum distance 33 # we relax all head vertices which are connected by that vertex 34 # heap should contain the distance and the tail vertex 35 # note that heap might contain distance values which are no longer valid due to relaxation 36 # we should remove those 37 minheap = [(0, k)] 38 while minheap: 39 prev_dist, u = heapq.heappop(minheap) 40 if prev_dist != dist[u]: 41 continue 42 for v, w in adj[u]: 43 relaxed = relax(dist, u, v, w) 44 if relaxed: 45 heapq.heappush(minheap, (dist[v], v)) 46 47 max_dist = max(dist[1:]) 48 return max_dist if max_dist < inf else -1
Why important: Many problems in real-world applications (e.g., routing, network optimization) rely on shortest paths.
Relevant Algorithms:
Dijkstra’s Algorithm (for non-negative weights).
Bellman-Ford Algorithm (for graphs with negative weights).
Floyd-Warshall Algorithm (all-pairs shortest paths).
A* Search (if heuristic-based optimization is required).
Example Problems:
Find the shortest path in a weighted directed graph.
Determine if a negative weight cycle exists.
Optimize routing in a graph with mixed positive and negative weights.
More Problems:
Problem: Given a weighted directed graph, find the shortest path from a source to a destination with at most \(k\) intermediate nodes.
Similar to the above, but you must use exactly \(k\) edges.
Detect if there’s a negative weight cycle and compute the shortest path in its presence (if possible).
Find the shortest path where certain nodes must or must not be visited.
Each edge can only be traversed a fixed number of times (e.g., roads with toll limits).
Find the shortest path where one edge’s weight can be reduced by a discount or percentage.
Edge weights vary based on the time of traversal (e.g., traffic at different times).
Find the shortest path that visits all nodes at least once.
Edge weights change dynamically during traversal (e.g., based on usage or traffic updates).
Compute the shortest path between multiple source-destination pairs.
Find the shortest path in a grid where some cells are blocked, and you can break at most \(k\) obstacles.
Different edge weights for different “modes” (e.g., car, bike, foot).
2. Minimum Spanning Tree (MST)¶
Sample implementation
MST algorithms
1""" Kruskal """ 2class UnionFind: 3 def __init__(self, n): 4 # every node is its own parent 5 self.parents = list(range(n)) 6 self.counts = [1] * n 7 8 # returns the root of the set that x belongs to 9 def find(self, x): 10 if self.parents[x] != x: 11 # resetting the parent pointers to all members of the set to reduce amortized cost 12 self.parents[x] = self.find(self.parents[x]) 13 return self.parents[x] 14 15 def union(self, x, y): 16 parent_x = self.find(x) 17 parent_y = self.find(y) 18 # whichever set is larger, that should be the root of the unioned set to reduce amortized cost 19 if self.counts[parent_x] > self.counts[parent_y]: 20 self.parents[parent_y] = parent_x 21 self.counts[parent_x] += self.counts[parent_y] 22 else: 23 self.parents[parent_x] = parent_y 24 self.counts[parent_y] += self.counts[parent_x] 25 26def kruskal(): 27 # sort the edges 28 # take each edge in sorted order 29 # add it to the tree if the other end doesn't already belong to the same group 30 # why do I need union find? why cannot we use a visited array? 31 # the way the algorithm works is because it forms a disjointed set of trees and then connecting them 32 # when connecting two disjointed sets, we need to ensure that we're not connecting within the same set 33 # that would form a cycle 34 disjoint_set = UnionFind(n + 1) 35 total_cost = 0 36 num_tree_edges = 0 37 38 for u, v, cost in sorted(connections, key=lambda x:x[2]): 39 if disjoint_set.find(u) != disjoint_set.find(v): 40 disjoint_set.union(u, v) 41 total_cost += cost 42 num_tree_edges += 1 43 44 return total_cost if num_tree_edges == n-1 else -1 45 46def build(n, connections): 47 adj = [[] for _ in range(n+1)] 48 for u, v, cost in connections: 49 adj[u].append((cost, v)) 50 adj[v].append((cost, u)) 51 return adj 52 53""" Prim """ 54def prim(): 55 adj = build(n, connections) 56 total_cost = 0 57 num_tree_edges = 0 58 # find all incident edges and mark them as candidates 59 # find the candidate with minimum weight 60 # go through the candidates from min weight to max one by one 61 # if the edge doesn't lead to another node which is visited, use the edge 62 # mark the vertex on the other end as visited so that we don't form circles 63 64 # need a visited array to avoid cycles 65 visited = [False] * (n + 1) 66 67 # need a minheap for storing the candidate edges 68 # need to store (cost, u, v) in the heap so that the mean is ordered by cost 69 minheap = [] 70 71 # start from node 1 72 visited[1] = True 73 74 for cost, v in adj[1]: 75 heapq.heappush(minheap, (cost, 1, v)) 76 77 # u should always be the one which is visited 78 # if v is also visited, then we remove this edge 79 while minheap: 80 # pop because the minimum edge is always removed 81 # either it forms part of the tree, or it is thrown away because adding it would form a cycle 82 cost, u, v = heapq.heappop(minheap) 83 if not visited[v]: 84 total_cost += cost 85 visited[v] = True 86 num_tree_edges += 1 87 88 for cost, w in adj[v]: 89 heapq.heappush(minheap, (cost, v, w)) 90 91 return total_cost if num_tree_edges == n-1 else -1
Why important: MSTs are useful in optimization problems, especially those involving connectivity.
Key Algorithms:
Prim’s Algorithm.
Kruskal’s Algorithm.
Example Problems:
Compute the MST for a weighted undirected graph.
Update the MST dynamically when a new edge is added.
Determine the second-best MST.
More Problems:
Find a minimum spanning tree, but the tree must include a specific edge \((u, v)\).
Find a spanning tree with the maximum total weight instead of the minimum.
Find the second smallest weight of a spanning tree (not the same as the minimum spanning tree).
Find a minimum spanning tree where no vertex can have a degree greater than k.
Each edge has an associated penalty if it is not included in the spanning tree. Find the tree that minimizes the sum of the MST weight and the penalties of excluded edges.
Find an MST where a specific vertex v must be part of the tree.
Each edge is assigned a color, and the MST must include at least one edge of every color.
You are given an MST for a graph. Process queries to either:
Add an edge and update the MST.
Remove an edge and update the MST.
Some edges have a discounted weight (e.g., weight reduced by x). Find the MST under the discounted weights.
Find the MST and also compute, for each edge in the MST, the cost of the MST if that edge is removed.
Find an MST in a graph that includes edges with negative weights.
Find an MST where the maximum depth of any vertex from the root is less than or equal to k.
3. Topological Sort¶
Sample implementation
Single source shortest path
1from collections import deque 2 3def kahn(): 4 # won't work if there are cycles 5 def build(n, edges): 6 in_degrees = [0] * n 7 adj = [[] for _ in range(n)] 8 for a, b in edges: 9 adj[b].append(a) 10 in_degrees[a] += 1 11 return adj, in_degrees 12 13 def bfs(): 14 nonlocal adj, visited, queue, tsorted, in_degrees 15 while queue: 16 u = queue.popleft() 17 tsorted.append(u) 18 for v in adj[u]: 19 in_degrees[v] -= 1 20 if not in_degrees[v]: 21 queue.append(v) 22 23 adj, in_degrees = build(numCourses, prerequisites) 24 visited = [False] * numCourses 25 26 queue = deque([]) 27 for u in range(numCourses): 28 if not in_degrees[u]: 29 visited[u] = True 30 queue.append(u) 31 32 tsorted = [] 33 if bfs(): 34 return [] 35 return tsorted if len(tsorted) == numCourses else [] 36 37def tarjan(): 38 # since this uses dfs, it can detect cycles 39 def build(n, edges): 40 adj = [[] for _ in range(n)] 41 for a, b in edges: 42 adj[b].append(a) 43 return adj 44 45 def has_cycle(u): 46 nonlocal visited, finished, adj, tsorted 47 visited[u] = True 48 for v in adj[u]: 49 if visited[v] and not finished[v]: # back edge 50 return True # cycle exists 51 if not visited[v] and has_cycle(v): 52 return True 53 finished[u] = True 54 tsorted.insert(0, u) 55 return False 56 57 adj = build(numCourses, prerequisites) 58 tsorted = [] 59 visited = [False] * numCourses 60 finished = [False] * numCourses 61 # no need to find root edges in the dag 62 # dfs would figure it out 63 for u in range(numCourses): 64 if not visited[u]: 65 # dfs returns true if there is a cycle, in which case it's not a dag 66 # we return empty list 67 if has_cycle(u): 68 return [] 69 return tsorted
Why important: Crucial for dependency resolution and scheduling problems.
Key Techniques:
Kahn’s Algorithm (BFS-based).
DFS with post-order traversal.
Example Problems:
Check if a directed graph has a cycle.
Compute a valid topological ordering.
Find the number of valid topological orderings.
4. Strongly Connected Components (SCCs)¶
Why important: SCCs are foundational in analyzing directed graphs for connectivity.
Key Algorithms:
Kosaraju’s Algorithm.
Tarjan’s Algorithm.
Example Problems:
Find all SCCs in a directed graph.
Determine if a graph is strongly connected.
Compute the smallest set of edges to make a graph strongly connected.
5. Bipartite Graphs¶
Why important: Common in matching and coloring problems.
Sample implementation
Using BFS and DFS
1def isBipartite(self, graph: List[List[int]]) -> bool: 2 def compliment(colour): 3 # returns 1 when colour = 0 4 # returns 0 when colour = 1 5 return 1 - colour 6 7 def using_bfs(): 8 n = len(graph) 9 colours = [2] * n # colour 2:= unvisited 10 11 def bfs(node): 12 nonlocal colours 13 queue = deque([node]) 14 15 while queue: 16 node = queue.popleft() 17 for child in graph[node]: 18 if colours[child] == colours[node]: 19 return False 20 if colours[child] == 2: 21 colours[child] = compliment(colours[node]) 22 queue.append(child) 23 return True 24 25 for node in range(n): 26 if colours[node] == 2: 27 colours[node] = 0 28 if not bfs(node): 29 return False 30 31 return True 32 33 def using_dfs(): 34 n = len(graph) 35 colours = [2] * n # colour 2:= unvisited 36 37 def dfs(node, parent): 38 nonlocal colours 39 40 for child in graph[node]: 41 if colours[child] == colours[node]: 42 return False 43 if child != parent and colours[child] == 2: 44 colours[child] = compliment(colours[node]) 45 if not dfs(child, node): 46 return False 47 48 return True 49 50 for node in range(n): 51 if colours[node] == 2: 52 colours[node] = 0 53 if not dfs(node, -1): 54 return False 55 56 return True
Key Techniques:
BFS/DFS to test bipartiteness.
Maximum Bipartite Matching using augmenting paths.
Example Problems:
Check if a graph is bipartite.
Solve matching problems in bipartite graphs.
Partition the graph into two disjoint sets.
6. Graph Traversals¶
Sample implementation
A collection of traversal algorithms and applications
1from collections import deque 2 3class Solution: 4 def bfs1(self, digraph, src): 5 n = len(digraph) 6 queue = deque([src]) 7 discovered = [False] * n 8 discovered[src] = True 9 vertices = [] 10 edges = [] 11 while queue: 12 u = queue.popleft() 13 vertices.append(u) 14 for v in digraph[u]: 15 edges.append((u, v)) 16 if not discovered[v]: 17 discovered[v] = True 18 queue.append(v) 19 return vertices, edges 20 21 def bfs2(self, graph, src): 22 n = len(graph) 23 queue = deque([src]) 24 discovered = [False] * n 25 processed = [False] * n 26 discovered[src] = True 27 vertices = [] 28 edges = [] 29 while queue: 30 u = queue.popleft() 31 vertices.append(u) 32 for v in graph[u]: 33 if not processed[v]: 34 edges.append((u, v)) 35 if not discovered[v]: 36 discovered[v] = True 37 queue.append(v) 38 processed[u] = True 39 return vertices, edges 40 41 def hasCycle(self, digraph, n): 42 def dfs(digraph, discovered, processed, u): 43 discovered[u] = True 44 for v in digraph.get(u, []): 45 if not discovered[v]: 46 if dfs(digraph, discovered, processed, v): 47 return True 48 elif not processed[v]: 49 return True 50 processed[u] = True 51 return False 52 discovered = [False] * n 53 processed = [False] * n 54 for u in range(n): 55 if not discovered[u] and dfs(digraph, discovered, processed, u): 56 return True 57 return False 58 59 def hasCycleUndirected(self, graph, n): 60 def dfs(graph, discovered, parent, u): 61 discovered[u] = True 62 for v in graph.get(u, []): 63 if parent == v: 64 continue 65 if discovered[v]: 66 return True 67 else: 68 if dfs(graph, discovered, u, v): 69 return True 70 return False 71 discovered = [False] * n 72 for u in range(n): 73 if not discovered[u] and dfs(graph, discovered, -1, u): 74 return True 75 return False 76 77 def isBipartite(self, graph, n): 78 colors = [None] * n 79 def bfs(graph, colors, src): 80 queue = deque([src]) 81 colors[src] = 0 82 while queue: 83 u = queue.popleft() 84 for v in graph.get(u, []): 85 if colors[v] is None: 86 colors[v] = colors[u] ^ 1 87 queue.append(v) 88 elif colors[v] == colors[u]: 89 return False 90 return True 91 for u in range(n): 92 if colors[u] is None and not bfs(graph, colors, u): 93 return False 94 return True 95 96 def findBCC(self, graph, n): 97 def dfs1(parent, u): 98 nonlocal discovered, entry, low, time, articulation, bridges 99 discovered[u] = True 100 low[u], entry[u] = time, time 101 time += 1 102 treedeg = 0 103 isArticulation = False 104 for v in graph.get(u, []): 105 if not discovered[v]: 106 treedeg += 1 107 dfs1(u, v) 108 low[u] = min(low[u], low[v]) 109 if low[v] > entry[u]: 110 bridges.append((u, v)) 111 if low[v] >= entry[u]: 112 isArticulation = True # parent articulation 113 elif parent != v: 114 low[u] = min(low[u], entry[v]) 115 if (parent == -1 and treedeg > 1) or (parent != -1 and isArticulation): 116 articulation.append(u) 117 def dfs2(parent, u, depth): 118 nonlocal discovered, entry, low, articulation, bridges 119 discovered[u] = True 120 low[u], entry[u] = depth, depth 121 treedeg = 0 122 isArticulation = False 123 for v in graph.get(u, []): 124 if not discovered[v]: 125 treedeg += 1 126 dfs2(u, v, depth + 1) 127 low[u] = min(low[u], low[v]) 128 if low[v] > entry[u]: 129 bridges.append((u, v)) 130 if low[v] >= entry[u]: 131 isArticulation = True # parent articulation 132 elif parent != v: 133 low[u] = min(low[u], entry[v]) 134 if (parent == -1 and treedeg > 1) or (parent != -1 and isArticulation): 135 articulation.append(u) 136 discovered = [False] * n 137 entry = [None] * n 138 low = [None] * n 139 articulation, bridges = [], [] 140 time = 0 141 for u in range(n): 142 if not discovered[u]: 143 dfs1(-1, u) 144 a, b = articulation, bridges 145 discovered = [False] * n 146 entry = [None] * n 147 low = [None] * n 148 articulation, bridges = [], [] 149 for u in range(n): 150 if not discovered[u]: 151 dfs2(-1, u, 0) 152 c, d = articulation, bridges 153 assert(a == c and b == d) 154 return articulation, bridges 155 def tsort(self, digraph, n): 156 if self.hasCycle(digraph, n): 157 return [] 158 def tarjan(): 159 order = [] 160 indeg = [0] * n 161 for u in digraph: 162 for v in digraph[u]: 163 indeg[v] += 1 164 queue = deque([x for x in range(n) if indeg[x] == 0]) 165 while queue: 166 u = queue.popleft() 167 order.append(u) 168 for v in digraph[u]: 169 indeg[v] -= 1 170 if indeg[v] == 0: 171 queue.append(v) 172 return order 173 def recursive(): 174 stack = [] 175 visited = [False] * n 176 def dfs(u): 177 nonlocal stack, visited 178 visited[u] = True 179 for v in digraph[u]: 180 if not visited[v]: 181 dfs(v) 182 stack.append(u) 183 for u in range(n): 184 if not visited[u]: 185 dfs(u) 186 stack.reverse() 187 return stack 188 order = tarjan() 189 stack = recursive() 190 return stack 191 192def digraphSearch(): 193 solution = Solution() 194 digraph = {0: [1, 2],1: [3, 4],2: [5, 6],3: [],4: [],5: [],6: []} 195 start_node = 0 196 res = solution.bfs1(digraph, start_node) 197 print(res) 198 199def undirectedGraphSearch(): 200 solution = Solution() 201 graph = {0: [1, 3],1: [0, 2],2: [1, 3],3: [0, 2]} 202 start_node = 0 203 res = solution.bfs2(graph, start_node) 204 print(res) 205 206def cycleDirected(): 207 solution = Solution() 208 digraph, n = {}, 0 # Should return False 209 res = solution.hasCycle(digraph, n) 210 print(res) 211 digraph, n = {0: []}, 1 # Should return False 212 res = solution.hasCycle(digraph, n) 213 print(res) 214 digraph, n = {0: [0]}, 1 # Should return True 215 res = solution.hasCycle(digraph, n) 216 print(res) 217 digraph, n = {0: [1], 1: []}, 2 # Should return False 218 res = solution.hasCycle(digraph, n) 219 print(res) 220 digraph, n = {0: [1], 1: [0]}, 2 # Should return True 221 res = solution.hasCycle(digraph, n) 222 print(res) 223 digraph, n = {0: [1], 2: [3], 3: []}, 4 # Should return False 224 res = solution.hasCycle(digraph, n) 225 print(res) 226 digraph, n = {0: [1], 1: [2], 2: [0], 3: [4], 4: []}, 5 # Should return True 227 res = solution.hasCycle(digraph, n) 228 print(res) 229 digraph, n = {0: [1], 1: [2], 3: []}, 4 # Should return False 230 res = solution.hasCycle(digraph, n) 231 print(res) 232 digraph, n = {0: [1, 2], 1: [3], 2: [3], 3: [4], 4: [2]}, 5 # Should return True 233 res = solution.hasCycle(digraph, n) 234 print(res) 235 236def cycleUndirected(): 237 solution = Solution() 238 graph, n = {}, 0 # Should return False 239 res = solution.hasCycleUndirected(graph, n) 240 print(res) 241 graph, n = {0: []}, 1 # Should return False 242 res = solution.hasCycleUndirected(graph, n) 243 print(res) 244 graph, n = {0: [0]}, 1 # Should return True 245 res = solution.hasCycleUndirected(graph, n) 246 print(res) 247 graph, n = {0: [1], 1: [0]}, 2 # Should return False 248 res = solution.hasCycleUndirected(graph, n) 249 print(res) 250 graph, n = {0: [1, 2], 1: [0, 2], 2: [0, 1]}, 3 # Should return True 251 res = solution.hasCycleUndirected(graph, n) 252 print(res) 253 graph, n = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2]}, 4 # Should return False 254 res = solution.hasCycleUndirected(graph, n) 255 print(res) 256 graph, n = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2], 4: [5], 5: [4, 6], 6: [5, 4]}, 7 # Should return True 257 res = solution.hasCycleUndirected(graph, n) 258 print(res) 259 graph, n = {0: [1, 1], 1: [0, 0]}, 2 # Should return True 260 res = solution.hasCycleUndirected(graph, n) 261 print(res) 262 graph, n = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3, 5], 5: [4]}, 6 # Should return True 263 res = solution.hasCycleUndirected(graph, n) 264 print(res) 265 graph, n = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 4], 4: [3, 5], 5: [4]}, 6 # Should return False 266 res = solution.hasCycleUndirected(graph, n) 267 print(res) 268 269def bipartite(): 270 solution = Solution() 271 graph, n = {}, 0 # Expected Output: True 272 res = solution.isBipartite(graph, n) 273 print(res) 274 graph, n = {0: []}, 1 # Expected Output: True 275 res = solution.isBipartite(graph, n) 276 print(res) 277 graph, n = {0: [1], 1: [0]}, 2, # Expected Output: True 278 res = solution.isBipartite(graph, n) 279 print(res) 280 graph, n = {0: [1, 2], 1: [0, 2], 2: [0, 1]}, 3 # Expected Output: False 281 res = solution.isBipartite(graph, n) 282 print(res) 283 graph, n = {0: [1, 3], 1: [0, 2], 2: [1, 3], 3: [0, 2]}, 4 # Expected Output: True 284 res = solution.isBipartite(graph, n) 285 print(res) 286 graph, n = {0: [1], 1: [0], 2: [3], 3: [2]}, 4 # Expected Output: True 287 res = solution.isBipartite(graph, n) 288 print(res) 289 graph, n = {0: [1], 1: [0], 2: [3, 4], 3: [2, 4], 4: [2, 3]}, 5 # Expected Output: False 290 res = solution.isBipartite(graph, n) 291 print(res) 292 graph, n = {0: [1, 2, 3, 4], 1: [0], 2: [0], 3: [0], 4: [0]}, 5 # Expected Output: True 293 res = solution.isBipartite(graph, n) 294 print(res) 295 graph, n = {0: [0]}, 1 # Expected Output: False 296 res = solution.isBipartite(graph, n) 297 print(res) 298 graph, n = {0: [1], 1: [0, 2], 2: [1, 3], 3: [2], 4: [5], 5: [4, 6], 6: [5]}, 7 # Expected Output: True 299 res = solution.isBipartite(graph, n) 300 print(res) 301 302def bcc(): 303 solution = Solution() 304 graph, n = {}, 0 # Expected Output: Bridges: [], Articulation Points: [] 305 res, res2 = solution.findBCC(graph, n) 306 print(res, res2) 307 graph, n = {0: []}, 1 # Expected Output: Bridges: [], Articulation Points: [] 308 res, res2 = solution.findBCC(graph, n) 309 print(res, res2) 310 graph, n = {0: [1], 1: [0]}, 2 # Expected Output: Bridges: [(0, 1)], Articulation Points: [] 311 res, res2 = solution.findBCC(graph, n) 312 print(res, res2) 313 graph, n = {0: [1], 1: [0, 2], 2: [1]}, 3 # Expected Output: Bridges: [(1, 2), (0, 1)], Articulation Points: [1] 314 res, res2 = solution.findBCC(graph, n) 315 print(res, res2) 316 graph, n = {0: [1, 2], 1: [0, 2], 2: [0, 1]}, 3 # Expected Output: Bridges: [], Articulation Points: [] 317 res, res2 = solution.findBCC(graph, n) 318 print(res, res2) 319 graph, n = {0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3]}, 5 # Expected Output: Bridges: [(0, 1), (1, 2), (3, 4)], Articulation Points: [1] 320 res, res2 = solution.findBCC(graph, n) 321 print(res, res2) 322 graph, n = {0: [1, 2], 1: [0, 2, 3], 2: [0, 1], 3: [1, 4], 4: [3]}, 5 # Expected Output: Bridges: [(1, 3), (3, 4)], Articulation Points: [1, 3] 323 res, res2 = solution.findBCC(graph, n) 324 print(res, res2) 325 graph, n = {0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3, 5], 5: [4]}, 6 # Expected Output: Bridges: [(0, 1), (1, 2), (3, 4), (4, 5)], Articulation Points: [1, 4] 326 res, res2 = solution.findBCC(graph, n) 327 print(res, res2) 328 graph, n = {0: [1, 2, 3, 4], 1: [0], 2: [0], 3: [0], 4: [0]}, 5 # Expected Output: Bridges: [(0, 1), (0, 2), (0, 3), (0, 4)], Articulation Points: [0] 329 res, res2 = solution.findBCC(graph, n) 330 print(res, res2) 331 graph, n = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3, 5], 5: [4]}, 6 # Expected Output: Bridges: [(3,4),(4, 5)], Articulation Points: [3, 4] 332 res, res2 = solution.findBCC(graph, n) 333 print(res, res2) 334 335def tsort(): 336 solution = Solution() 337 graph, n = {0: [1, 2], 1: [2, 3], 2: [3], 3: []}, 4 # Expected output: [0, 1, 2, 3] 338 print(solution.tsort(graph, n)) 339 graph, n = {0: [1], 1: [2], 2: [3], 3: []}, 4 # Expected output: [0, 1, 2, 3] 340 print(solution.tsort(graph, n)) 341 graph, n = {0: [1], 1: [2], 2: [0]}, 3 # Expected output: None (Cycle detected, no topological sort possible) 342 print(solution.tsort(graph, n)) 343 graph, n = {0: [], 1: [0], 2: [1], 3: [1]}, 4 # Expected output: [3, 2, 1, 0] or [2, 3, 1, 0] 344 print(solution.tsort(graph, n)) 345 graph, n = {0: [], 1: [2], 2: [3], 3: [4], 4: []}, 5 # Expected output: [1, 2, 3, 4, 0] or any valid topological order 346 print(solution.tsort(graph, n)) 347 graph, n = {0: [1], 1: [], 2: [3], 3: [], 4: [1, 3]}, 5 # Expected output: [4, 0, 2, 3, 1] or any valid topological order 348 print(solution.tsort(graph, n)) 349 350if __name__ == '__main__': 351 digraphSearch() 352 undirectedGraphSearch() 353 cycleDirected() 354 cycleUndirected() 355 bipartite() 356 bcc() 357 tsort()
Bidirectional BFS
Word Ladder
Multi Source BFS
Rotting Oranges
1def orangesRotting(self, grid: List[List[int]]) -> int: 2 m, n = len(grid), len(grid[0]) if len(grid) > 0 else 0 3 4 queue = deque() 5 fresh_count = 0 6 7 for i in range(m): 8 for j in range(n): 9 if grid[i][j] == 2: 10 queue.append((i,j)) 11 elif grid[i][j] == 1: 12 fresh_count += 1 13 14 directions = [(-1,0),(1,0),(0,-1),(0,1)] 15 16 def next_direction(x, y, direction): 17 return x + direction[0], y + direction[1] 18 19 def within_boundaries(x, y): 20 nonlocal m, n 21 return 0 <= x and x < m and 0 <= y and y < n 22 23 steps = 0 24 25 while queue and fresh_count: 26 size = len(queue) 27 for _ in range(size): 28 i, j = queue.popleft() 29 for direction in directions: 30 x, y = next_direction(i, j, direction) 31 if within_boundaries(x, y) and grid[x][y] == 1: 32 fresh_count -= 1 33 grid[x][y] = 2 34 queue.append((x, y)) 35 steps += 1 36 37 return steps if not fresh_count else -1
Why important: Breadth-first and depth-first searches are foundational for exploring graphs.
Key Techniques:
BFS (used for shortest paths in unweighted graphs, connected components).
DFS (used for cycle detection, pathfinding, and SCCs).
Example Problems:
Find all connected components.
Detect cycles in a directed or undirected graph.
Implement BFS/DFS to solve maze problems.
7. Dynamic Graph Algorithms¶
Why important: Company values efficiency, and dynamic updates test your ability to optimize graph data structures.
Key Problems:
Maintain connectivity as edges are added or removed.
Recompute shortest paths or MST dynamically.
Optimize graph updates in streaming contexts.
8. Network Flow¶
Why important: Advanced but occasionally tested for senior-level candidates to assess problem-solving depth.
Key Algorithms:
Ford-Fulkerson Algorithm.
Edmonds-Karp Algorithm.
Example Problems:
Compute maximum flow in a flow network.
Solve bipartite matching using flow techniques.
Minimize the cut in a weighted graph.
9. Eulerian and Hamiltonian Paths¶
Why important: Rare but can appear in challenging questions.
Example Problems:
Determine if a graph has an Eulerian path or circuit.
Find the Hamiltonian path if it exists.
Compute a path visiting all edges or vertices exactly once.
10. Advanced Graph Techniques¶
Why important: Tests your depth of knowledge for senior-level positions.
Key Areas:
Articulation Points and Bridges.
Graph Coloring Problems.
Spectral Graph Theory (rare but valuable for specific roles).
More Problems:
Determine the chromatic number of a graph, i.e., the minimum number of colors required to color the graph such that no two adjacent vertices share the same color.
Check if a graph is bipartite by verifying if it can be colored using exactly two colors.
Assign colors to edges such that no two edges sharing the same vertex have the same color. Minimize the number of colors used.
Color a graph such that certain vertices have preassigned colors or cannot use specific colors.
Assign colors such that no two vertices at a distance of 1 (adjacent) or distance of 2 (neighbors’ neighbors) share the same color.
Assign colors to vertices such that the sum of the weights of conflicting edges is minimized.
Given a fixed number of colors, determine if the graph can be properly colored.
Assign colors to vertices such that the difference between the colors of adjacent vertices satisfies specific modular constraints.
Color a planar graph with a maximum of 4 colors (Four Color Theorem).
Maintain a valid coloring of a graph while allowing for vertex or edge insertions and deletions.
11. All Topics¶
You are given a directed graph where each node represents a city and edges represent roads between them with a time cost. Find the smallest time to travel between two given cities, but you can use a “shortcut” road that reduces the time of any one edge to zero.
A maze is represented as a grid. Each cell is either walkable or a wall. Find the minimum number of walls you must break to create a path from the top-left corner to the bottom-right corner.
You are given a graph with nn nodes and mm edges, where each edge has a weight. Determine if there exists a subset of edges such that the graph becomes a tree and the sum of weights is odd.
You are tasked to partition a graph into two subgraphs such that the difference in the number of nodes between the two subgraphs is minimized.
In a large social network graph, find the smallest group of people (nodes) such that every other person in the network is directly connected to at least one person in this group.
Find the longest path in a Directed Acyclic Graph (DAG) where all nodes must be visited exactly once.
Given a weighted undirected graph, find the number of distinct Minimum Spanning Trees (MSTs) that can be formed.
You are given a graph where each node has a value. Find the largest sum of values that can be obtained by traversing from a given start node to an end node while following the graph’s edges.
You are given a directed graph representing a city’s one-way road system. Each node represents an intersection, and each edge represents a road. Due to construction, one road (edge) can be closed. Determine whether the city remains fully connected (i.e., you can still reach all intersections from any starting intersection) if any one road is removed.
You are given an undirected graph representing a set of servers connected by cables. A server is considered critical if removing it causes some servers to become disconnected. Find all the critical servers in the graph.
A company wants to install a messaging system in its office building. The building is represented as a weighted undirected graph, where nodes are rooms and edges are connections between rooms. Messages can only travel over edges. Determine the minimum set of edges to remove such that there is no path between two specific rooms while keeping the rest of the graph connected.
You are given a directed acyclic graph (DAG) where each node represents a task, and each edge (u, v) means task u must be completed before task v. Multiple workers are available to work on tasks simultaneously. Each task takes exactly 1 unit of time to complete. Calculate the minimum time required to complete all tasks.
Given a grid with n rows and m columns, each cell is either land (1) or water (0). You can traverse only horizontally or vertically. A bridge can be built between two pieces of land separated by water if the Manhattan distance between them is 1. Determine the minimum number of bridges needed to connect all pieces of land into a single connected component.
A tournament is represented as a directed graph, where each edge (u, v) means team u defeated team v. Some match results are missing, represented as missing edges. Determine if it is possible to orient the missing edges such that the resulting graph is still a tournament.
You are given an undirected graph representing a city’s sewer system, where nodes are sewer junctions and edges are pipes connecting them. Certain pipes are old and at risk of breaking. Find the minimum number of new pipes that need to be added to ensure that no single pipe failure disconnects any part of the system.
You are given a weighted undirected graph representing a network of computers. Some edges are “critical” (important for connectivity), and some are “pseudo-critical” (important but can be replaced by other edges). Write an algorithm to classify each edge as critical, pseudo-critical, or neither.
You are given a directed graph where each edge has an initial cost. You can choose to reduce the weight of up to \(k\) edges by half. Find the minimum total cost to travel between two given nodes after applying this optimization.
You are given a directed graph where some edges have been removed, resulting in a disconnected graph. Determine the minimum number of edges to add back to restore strong connectivity.
You are given an undirected graph with \(n\) nodes. The graph is subject to operations of two types: 1. Add an edge between two nodes. 2. Check if two nodes are in the same connected component. Implement an algorithm to handle these operations efficiently.
Given a directed acyclic graph (DAG) where each edge has a weight and a constraint \(k\), find the maximum sum of weights for any path containing at most \(k\) edges.
A city is represented as a weighted grid where each cell has an elevation. Water floods from a source cell and can only flow to adjacent cells with equal or lower elevation. Determine the total area of cells that will be flooded.
You are given an undirected graph representing a network of roads between cities. A road is considered “critical” if removing it increases the shortest path between any two cities. Identify all critical roads in the graph.
You are given a directed graph with \(n\) nodes and \(m\) edges. Some edges are “mandatory,” and others are “optional.” Determine if it’s possible to orient the optional edges to form a directed acyclic graph (DAG).
A company plans to expand its network by adding new connections. Each connection has a cost, and the company has a fixed budget. Find the maximum number of nodes that can be connected to the network within the budget.
You are given a directed graph where each node can serve as a starting point for spreading information. Calculate the minimum time required for information to reach all nodes, assuming it spreads simultaneously from all sources.
Given an undirected graph, color its nodes using the minimum number of colors such that no two adjacent nodes have the same color. Additionally, certain nodes have preassigned colors, and the coloring must respect these assignments.
You are given a directed graph where some nodes act as sources and others as sinks. Find the maximum flow in the network, assuming flow can originate from multiple sources and terminate at multiple sinks.
You are given a weighted undirected graph and a threshold \(t\). Form clusters by removing edges with weights greater than \(t\). Calculate the number of resulting clusters and the size of the largest cluster.
You are given a list of shortest paths between all pairs of nodes in an undirected graph. Determine if it is possible to reconstruct the original graph. If multiple graphs are possible, return any valid one.
You are given a directed graph where each edge has a delay time. Calculate the minimum total delay required to synchronize all nodes such that every node receives a signal at the same time.
A travel route is represented as a directed graph with costs on edges. You must visit certain mandatory nodes exactly once in any order. Find the shortest path that satisfies these constraints.
Given a directed graph, a source node, and a destination node, find the \(k\)-th shortest path from the source to the destination.
You are given an undirected graph. Determine the minimum number of nodes that must be removed so that the remaining graph is still fully connected.
A road network is represented as a weighted undirected graph. Each road has a traffic limit. Determine if it is possible to reroute all vehicles such that the traffic on no road exceeds its limit.
You are given a weighted directed graph. Find the minimum weight cycle (if it exists) and return its weight. If no cycle exists, return -1.
You are given an undirected graph. Remove the minimum number of edges to partition the graph into two disjoint connected components of equal size (or as close as possible).
12. Multi-Step Problems¶
Verifying and Improving Connectivity
The police department in the city has converted every street into a one-way road. The mayor claims that it is possible to legally drive from any intersection in the city to any other intersection.
Verify Strong Connectivity: Design an algorithm to determine whether the city is strongly connected. If it is not, refute the mayor’s claim.
Good Intersections: Call an intersection \(x\) good if, for any intersection \(y\) that one can legally reach from \(x\), it is possible to legally drive from \(y\) back to \(x\). The mayor further claims that over 95% of the intersections in Sham-Poobanana are good. Devise an algorithm to verify or refute this claim.
Reachability Pairs: Count the number of pairs of intersections \((A, B)\) where \(A\) can reach \(B\), but \(B\) cannot reach \(A\).
Maximum Reachability Intersection: Find the intersection with the highest reachability, defined as the number of intersections reachable from it.
Restoring Strong Connectivity: Determine the minimum number of streets that need to be converted back to two-way roads to make the city strongly connected.
Signage Changes with Minimum Hires: People can be hired at intersections to convert roads back to two-way streets. They must obey traffic laws while doing so (i.e., they can only travel back on a street after making it two-way). Devise an efficient algorithm to minimize the number of people hired and provide an order of operations for each person to change signage.