This is the companion piece for the above video. Below are four snippets, in the order they appear on screen: the BFS template, the number of islands solution, the DFS template, and the course schedule cycle-detection solution. No extra commentary here beyond what you need to read the code.
If you want the full walkthrough of the decisions behind each one, that’s in the video.
BFS template
The skeleton to have memorized. Visited set initialized before the loop, nodes marked visited when they’re added to the queue (not when they’re processed), and `popleft` on a deque instead of `pop` on a list, since `popleft` is O(1).
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
# process node here
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)Number of islands (BFS)
Given an m by n grid of 0s and 1s, count the number of islands -- groups of connected 1s, connected horizontally or vertically.
def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
islands = 0
def bfs(r, c):
queue = deque([(r, c)])
visited.add((r, c))
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
row, col = queue.popleft()
for dr, dc in directions:
nr, nc = row + dr, col + dc
if (nr, nc) not in visited \
and 0 <= nr < rows \
and 0 <= nc < cols \
and grid[nr][nc] == "1":
queue.append((nr, nc))
visited.add((nr, nc))
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in visited:
bfs(r, c)
islands += 1
return islandsThe outer loop is what handles disconnected islands -- every unvisited “1” starts a fresh BFS. This pattern transfers directly to number of connected components, flood fill, and Pacific Atlantic water flow.
DFS template
Same shape as BFS, but recursion replaces the queue, and the visited check happens at the top of the function rather than before the recursive call.
def dfs(graph, node, visited):
if node in visited:
return
visited.add(node)
# process node here
for neighbor in graph[node]:
dfs(graph, neighbor, visited)Course schedule (DFS cycle detection)
Given `numCourses` and a list of prerequisite pairs `[course, prereq]`, determine whether it’s possible to finish all courses -- i.e., whether the prerequisite graph has a cycle. This is the problem where DFS isn’t just an option, it’s the natural tool: the recursion call stack is the current path, so checking “is this node an ancestor of itself” falls out of the traversal for free.
def canFinish(numCourses, prerequisites):
graph = {i: [] for i in range(numCourses)}
for course, prereq in prerequisites:
graph[course].append(prereq)
# 0 = unvisited, 1 = in current path, 2 = fully cleared
state = [0] * numCourses
def dfs(course):
if state[course] == 1:
return False # back edge -- cycle found
if state[course] == 2:
return True # already verified safe
state[course] = 1
for prereq in graph[course]:
if not dfs(prereq):
return False
state[course] = 2
return True
return all(dfs(course) for course in range(numCourses))The three states are the key idea: a plain visited set only tells you “have I seen this node ever.” Here you need “is this node still on my current path,” which is what state 1 tracks. That’s also the backbone of topological sort -- append each node to a result list right after marking it state 2, and this becomes a new version (Course Schedule II).
Full breakdown of when to reach for each of these, and the mistakes that cost senior candidates points, in the video. Next up in the series: heaps.