Nodes + edges. BFS = shortest path (unweighted). DFS = connected components, cycle detection, topological sort.
[]| Use BFS when... | Use DFS when... |
|---|---|
| Shortest path (unweighted) | Connected components |
| Level-order traversal | Cycle detection |
| Minimum steps to reach target | Topological sort |
| Closest neighbor | Path exists (yes/no) |
Find valid ordering where every prerequisite comes before the course. Start from nodes with in-degree=0.
from collections import deque, defaultdict # Build adjacency list graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) # undirected # BFS — shortest path def bfs(graph, start, target): q, visited, dist = deque([(start, 0)]), {start}, {} while q: node, d = q.popleft() if node == target: return d for nei in graph[node]: if nei not in visited: visited.add(nei); q.append((nei, d+1)) # DFS — iterative with stack def dfs(graph, start): stack, visited = [start], {start} while stack: node = stack.pop() for nei in graph[node]: if nei not in visited: visited.add(nei); stack.append(nei)
def topo_sort(numNodes, edges): graph = defaultdict(list) in_degree = [0] * numNodes for u, v in edges: graph[u].append(v); in_degree[v] += 1 q = deque(i for i in range(numNodes) if in_degree[i] == 0) result = [] while q: node = q.popleft(); result.append(node) for nei in graph[node]: in_degree[nei] -= 1 if in_degree[nei] == 0: q.append(nei) # if len(result) < numNodes → cycle! return result if len(result) == numNodes else []