图的 BFS 与 DFS

图的表示

• 邻接表：graph[u] = [v1, v2]，稀疏图省空间，遍历 u 的邻居 O(度)。
• 邻接矩阵：g[u][v]，稠密图或需 O(1) 判边存在。

面试多数用邻接表 + defaultdict(list) 或 vector 数组。

DFS：深度优先

用于连通性、路径存在、拓扑（递归）、岛屿数量、回溯式搜索。

def dfs(graph, start, visited):
    visited.add(start)
    for nei in graph[start]:
        if nei not in visited:
            dfs(graph, nei, visited)
def num_islands(grid):
    rows, cols = len(grid), len(grid[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"
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(r + dr, c + dc)
count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                dfs(r, c)
                count += 1
    return count

三色 DFS 判环（有向图）：0 未访，1 访问中，2 完成；遇到 1 说明后向边，有环。

BFS：广度优先

用队列按层扩展，适合最短步数、多源 BFS、层次遍历。

from collections import deque
def bfs_shortest_steps(graph, start, target):
    q = deque([(start, 0)])
    visited = {start}
    while q:
        node, dist = q.popleft()
        if node == target:
            return dist
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                q.append((nei, dist + 1))
    return -1

多源 BFS：把所有源点同时入队，dist=0，一起扩散（腐烂橘子、01 矩阵到最近 0 的距离）。

拓扑排序（Kahn / DFS）

有向无环图（DAG）的线性序，使每条边 u→v 中 u 在 v 前。

Kahn（BFS）：入度为 0 入队，弹出时减邻居入度，入度变 0 再入队；若处理节点数 < n 则有环。

def topo_sort(n, edges):
    indeg = [0] * n
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []

选题对照

| 需求 | 算法 | |---|---| | 层数/最短步 | BFS | | 连通块、路径、环 | DFS | | 课程表、依赖 | 拓扑 | | 带权最短路 | Dijkstra / SPFA |

练习：200、695、133、207、210、994、542。写题时先说明有向/无向、权值，再选 BFS 或 DFS，避免混用模板。