Graphs: BFS, DFS & Shortest Paths

Concept

Store graphs as an adjacency list: a map from each node to its neighbours. Grids are graphs too (4 neighbours per cell).

BFS explores level by level with a queue and finds the shortest path in unweighted graphs. DFS goes deep using recursion or a stack.

Topological sort orders tasks with dependencies (Kahn's algorithm uses in-degrees). Dijkstra finds shortest paths with non-negative weights using a heap.

Complexity

Code (Python)

from collections import deque

def num_islands(grid):
    rows, cols, count = len(grid), len(grid[0]), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                q = deque([(r, c)])
                grid[r][c] = "0"
                while q:
                    x, y = q.popleft()
                    for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1":
                            grid[nx][ny] = "0"
                            q.append((nx, ny))
    return count

Remember

• Track visited nodes to avoid infinite loops.
• Shortest path, unweighted → BFS.
• Dependencies / ordering → topological sort.