BFS and DFS are the most important graph algorithms for coding interviews. In the earlier graphs article, we covered the basics. Now we go deeper: Dijkstra’s algorithm for weighted shortest paths, multi-source BFS, matrix-as-graph problems, and the most common patterns you will see in interviews.
We show every example in Kotlin, Python, and Go.
BFS Patterns
Pattern 1: Shortest Path in Unweighted Graph
BFS finds the shortest path in unweighted graphs because it explores nodes level by level. Every node at distance d is visited before any node at distance d+1.
Python:
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
return -1 # No path
Pattern 2: Level-Order Processing
Process all nodes at the same level together. Track the level by processing the entire queue at each step.
Python:
from collections import deque
def bfs_by_level(graph, start):
queue = deque([start])
visited = {start}
level = 0
while queue:
size = len(queue)
for _ in range(size): # Process all nodes at current level
node = queue.popleft()
print(f"Level {level}: {node}")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
level += 1
Pattern 3: Multi-Source BFS
Start BFS from multiple sources simultaneously. All sources are added to the queue at the beginning.
Rotting Oranges: Every minute, fresh oranges adjacent to rotten ones become rotten. Find the minimum time until all oranges are rotten.
Python:
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Add all rotten oranges to queue (multi-source)
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
if fresh == 0:
return 0
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
max_time = 0
while queue:
r, c, time = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
max_time = max(max_time, time + 1)
queue.append((nr, nc, time + 1))
return max_time if fresh == 0 else -1
Kotlin:
fun orangesRotting(grid: Array<IntArray>): Int {
val rows = grid.size
val cols = grid[0].size
val queue: ArrayDeque<Triple<Int, Int, Int>> = ArrayDeque()
var fresh = 0
for (r in 0 until rows) {
for (c in 0 until cols) {
if (grid[r][c] == 2) queue.add(Triple(r, c, 0))
else if (grid[r][c] == 1) fresh++
}
}
if (fresh == 0) return 0
val dirs = arrayOf(intArrayOf(0, 1), intArrayOf(0, -1), intArrayOf(1, 0), intArrayOf(-1, 0))
var maxTime = 0
while (queue.isNotEmpty()) {
val (r, c, time) = queue.removeFirst()
for ((dr, dc) in dirs) {
val nr = r + dr
val nc = c + dc
if (nr in 0 until rows && nc in 0 until cols && grid[nr][nc] == 1) {
grid[nr][nc] = 2
fresh--
maxTime = maxOf(maxTime, time + 1)
queue.add(Triple(nr, nc, time + 1))
}
}
}
return if (fresh == 0) maxTime else -1
}
Time: O(m * n). Space: O(m * n).
Dijkstra’s Algorithm
For weighted graphs with non-negative weights, Dijkstra’s algorithm finds the shortest path using a priority queue (min-heap).
Python:
import heapq
def dijkstra(graph, start):
# graph = {node: [(neighbor, weight), ...]}
distances = {node: float("inf") for node in graph}
distances[start] = 0
heap = [(0, start)] # (distance, node)
while heap:
dist, node = heapq.heappop(heap)
if dist > distances[node]:
continue # Already found a shorter path
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distances
Kotlin:
import java.util.PriorityQueue
fun dijkstra(graph: Map<Int, List<Pair<Int, Int>>>, start: Int): Map<Int, Int> {
val distances = mutableMapOf<Int, Int>().withDefault { Int.MAX_VALUE }
distances[start] = 0
val heap = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
heap.add(Pair(0, start))
while (heap.isNotEmpty()) {
val (dist, node) = heap.poll()
if (dist > distances.getValue(node)) continue
for ((neighbor, weight) in graph[node] ?: emptyList()) {
val newDist = dist + weight
if (newDist < distances.getValue(neighbor)) {
distances[neighbor] = newDist
heap.add(Pair(newDist, neighbor))
}
}
}
return distances
}
Go:
import "container/heap"
type Edge struct {
node, weight int
}
type Item struct {
node, dist int
}
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
item := old[n-1]
*h = old[:n-1]
return item
}
func dijkstra(graph map[int][]Edge, start int, n int) []int {
dist := make([]int, n)
for i := range dist {
dist[i] = 1<<63 - 1
}
dist[start] = 0
h := &MinHeap{{start, 0}}
heap.Init(h)
for h.Len() > 0 {
curr := heap.Pop(h).(Item)
if curr.dist > dist[curr.node] {
continue
}
for _, edge := range graph[curr.node] {
newDist := curr.dist + edge.weight
if newDist < dist[edge.node] {
dist[edge.node] = newDist
heap.Push(h, Item{edge.node, newDist})
}
}
}
return dist
}
Time: O((V + E) log V) with a binary heap. Space: O(V + E).
Network Delay Time
Find the time for a signal to reach all nodes from a source node.
Python:
import heapq
def network_delay_time(times, n, k):
graph = {i: [] for i in range(1, n + 1)}
for u, v, w in times:
graph[u].append((v, w))
dist = {i: float("inf") for i in range(1, n + 1)}
dist[k] = 0
heap = [(0, k)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
max_dist = max(dist.values())
return max_dist if max_dist < float("inf") else -1
DFS Patterns
Pattern 1: Connected Components (Number of Islands)
Treat a 2D grid as an implicit graph. Each cell is a node, and adjacent cells are neighbors.
Python:
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0" # Mark as visited
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
count += 1
dfs(r, c)
return count
Go:
func numIslands(grid [][]byte) int {
if len(grid) == 0 {
return 0
}
rows, cols := len(grid), len(grid[0])
count := 0
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1' {
return
}
grid[r][c] = '0'
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
}
for r := 0; r < rows; r++ {
for c := 0; c < cols; c++ {
if grid[r][c] == '1' {
count++
dfs(r, c)
}
}
}
return count
}
Pattern 2: Path Finding
Find all paths or check if a path exists.
Python:
def all_paths_source_target(graph):
# graph[i] = list of nodes reachable from i
result = []
target = len(graph) - 1
def dfs(node, path):
if node == target:
result.append(path[:])
return
for neighbor in graph[node]:
path.append(neighbor)
dfs(neighbor, path)
path.pop()
dfs(0, [0])
return result
Pattern 3: Cycle Detection
Directed graph cycle detection with DFS colors:
Python:
def has_cycle_directed(graph, n):
# 0 = unvisited, 1 = in progress, 2 = done
color = [0] * n
def dfs(node):
color[node] = 1
for neighbor in graph[node]:
if color[neighbor] == 1:
return True # Back edge = cycle
if color[neighbor] == 0 and dfs(neighbor):
return True
color[node] = 2
return False
for i in range(n):
if color[i] == 0 and dfs(i):
return True
return False
When to Use BFS vs DFS vs Dijkstra
| Situation | Use |
|---|---|
| Shortest path, unweighted | BFS |
| Shortest path, weighted (non-negative) | Dijkstra |
| Shortest path, negative weights | Bellman-Ford |
| All paths / any path | DFS |
| Connected components | DFS or BFS |
| Cycle detection | DFS |
| Topological sort | DFS or BFS (Kahn’s) |
| Level-order processing | BFS |
| Minimum steps / moves | BFS |
Word Ladder
Transform one word into another, changing one letter at a time. Each intermediate word must be a valid word. Find the shortest transformation.
Python:
from collections import deque
def ladder_length(begin_word, end_word, word_list):
word_set = set(word_list)
if end_word not in word_set:
return 0
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
word, length = queue.popleft()
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + c + word[i + 1:]
if next_word == end_word:
return length + 1
if next_word in word_set and next_word not in visited:
visited.add(next_word)
queue.append((next_word, length + 1))
return 0
Time: O(n * m * 26) where n = number of words, m = word length. This uses BFS because we need the shortest path.
Common Mistakes
Using DFS for shortest path in unweighted graphs. DFS does not guarantee shortest path. Use BFS.
Forgetting to mark nodes as visited. Without marking, you get infinite loops in graphs with cycles.
Modifying the grid during BFS without proper handling. If you modify the grid as you add to the queue (correct), not when you process (incorrect), you avoid adding duplicates.
Using Dijkstra with negative weights. Dijkstra does not work with negative edges. Use Bellman-Ford instead.
Practice Problems
| Problem | Pattern | LeetCode # |
|---|---|---|
| Number of Islands | DFS connected components | #200 |
| Rotting Oranges | Multi-source BFS | #994 |
| Word Ladder | BFS shortest path | #127 |
| Network Delay Time | Dijkstra | #743 |
| Pacific Atlantic Water Flow | DFS from borders | #417 |
| Course Schedule II | Topological sort | #210 |
| Clone Graph | BFS or DFS | #133 |
| Surrounded Regions | DFS from borders | #130 |
What’s Next?
You now know the core algorithms. The next part of this series focuses on Interview Patterns — starting with the Top 10 LeetCode Patterns that solve 87% of interview questions.
Next: DSA Tutorial #19: Top 10 LeetCode Patterns
Full series: DSA from Zero to Interview Ready