图

图

图（graph）用来建模关系和连接，从社交网络到路网再到依赖链。本文件涵盖图的表示、BFS、DFS、最短路径、拓扑排序和连通分量，以及主宰图论面试题的遍历与寻路模式。

• 我们在第 12 章和第 13 章讲过图论（邻接矩阵、拉普拉斯矩阵、谱性质，以及树、平面性、着色）。这里我们聚焦于算法模式：如何用代码遍历、搜索和在图上做优化。

• 两个最基本的图算法是 BFS 和 DFS。几乎每个图问题都能归结为这两者之一（可能带些改造）。掌握这两个，你就能解决绝大多数图问题。

图的表示

• 邻接表（adjacency list）：对每个节点，存它的邻居列表。空间：O(|V| + |E|)。最适合稀疏图（大多数真实世界的图）。

# 无向图
graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3],
    3: [1, 2]
}

# 从边列表构造
def build_graph(n, edges):
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # 有向图去掉这一行
    return graph
​

• 邻接矩阵（adjacency matrix）：n \times n 的矩阵，若边 (i, j) 存在则 A[i][j] = 1。空间：O(|V|^2)。最适合稠密图，或需要 O(1) 查询边是否存在时。

• 何时用哪个：几乎什么都用邻接表。只有当图很稠密（|E| \approx |V|^2）或需要常数时间检查边是否存在时才用矩阵。

模式：BFS（广度优先搜索）

• BFS 用一个队列逐层探索节点。它是以下场景的首选算法：
  • 无权图中的最短路径
  • 层序遍历
  • 找连通分量
  • 任何问「最少步数」的问题

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbour in graph[node]:
            if neighbour not in visited:
                visited.add(neighbour)
                queue.append(neighbour)
​

• 关键：在入队时就标记 visited，而不是出队时。如果你在出队时才标记，同一个节点可能被不同前驱多次入队，浪费时间并可能导致错误结果。

简单：岛屿数量

• 题目：给定一个由 '1'（陆地）和 '0'（水）组成的 2D 网格，统计岛屿数量。

• 模式：遍历网格。找到一个 '1' 时，用 BFS/DFS 把所有连通的陆地格子标记为已访问。每次启动 BFS 就是一座岛。

from collections import deque

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                # 用 BFS 标记整座岛
                queue = deque([(r, c)])
                grid[r][c] = '0'  # 标记已访问
                while queue:
                    cr, cc = queue.popleft()
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nr, nc = cr + dr, cc + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'
                            queue.append((nr, nc))

    return count
​

• 陷阱：directions = [(0,1),(0,-1),(1,0),(-1,0)] 这个 4 连通网格邻居的模式几乎用在每一道网格题里。记牢它。要 8 连通，加上对角线。

• 陷阱：直接修改输入网格（grid[r][c] = '0'）可以避免单独开一个 visited 集合。面试中可以接受，但要明确说明代价（会改动输入）。

中等：腐烂的橘子

• 题目：新鲜的橘子如果与腐烂的橘子相邻就会腐烂。返回所有橘子腐烂所需的最短时间（不可能则返回 -1）。

• 模式：多源 BFS。把所有初始就腐烂的橘子同时放进队列。每个 BFS 层就是一个时间步。

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    time = 0
    while queue and fresh > 0:
        time += 1
        for _ in range(len(queue)):
            cr, cc = queue.popleft()
            for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return time if fresh == 0 else -1
​

• 关键洞见：多源 BFS 同时处理所有源。这给出的是到任意源的最短距离，正好对应「最后一个新鲜橘子什么时候腐烂」。

模式：DFS（深度优先搜索）

• DFS 尽可能深地探索，然后再回溯。它用栈（显式栈或递归的调用栈）。DFS 是以下场景的首选：
  • 环检测
  • 拓扑排序
  • 连通分量
  • 回溯 / 穷举搜索
  • 带约束的寻路

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited)
​

中等：课程表（环检测）

• 题目：给定 n 门课和先修关系，判断是否能修完所有课（即没有循环依赖）。

• 模式：在有向图中检测环。用三种状态的 DFS：未访问、进行中（在当前 DFS 路径上）、已完成。

def can_finish(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    for course, prereq in prerequisites:
        graph[course].append(prereq)

    # 0 = 未访问，1 = 进行中，2 = 已完成
    state = [0] * num_courses

    def has_cycle(node):
        if state[node] == 1:
            return True   # 回边 → 环
        if state[node] == 2:
            return False  # 已经完整探索过

        state[node] = 1  # 标记进行中
        for neighbour in graph[node]:
            if has_cycle(neighbour):
                return True
        state[node] = 2  # 标记已完成
        return False

    for course in range(num_courses):
        if has_cycle(course):
            return False
    return True
​

• 为什么要三种状态：两种状态（已访问/未访问）无法区分「我正在探索这个节点」和「我已经探索完这个节点」。遇到一个正在被探索的节点（状态 = 1）意味着找到了环。遇到一个已完成的节点（状态 = 2）只是一条横跨边，不是环。

中等：课程表 II（拓扑排序）

• 题目：返回一个合法的修课顺序（拓扑序）。

• 模式（Kahn 算法——基于 BFS）：从没有入边（入度为 0）的节点开始。处理它们，减少其邻居的入度。重复。

from collections import deque

def find_order(num_courses, prerequisites):
    graph = {i: [] for i in range(num_courses)}
    indegree = [0] * num_courses

    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(num_courses) if indegree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            indegree[neighbour] -= 1
            if indegree[neighbour] == 0:
                queue.append(neighbour)

    return order if len(order) == num_courses else []  # 为空 = 存在环
​

• 陷阱：如果结果里的节点数比图里少，说明存在环（某些节点的入度永远降不到 0）。

最短路径

Dijkstra 算法

• 在非负加权图中，求从源点到所有其他节点的最短路径。用一个优先队列（最小堆）。

import heapq

def dijkstra(graph, start):
    # graph: {节点: [(邻居, 权重), ...]}
    dist = {node: float('inf') for node in graph}
    dist[start] = 0
    heap = [(0, start)]

    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue  # 陈旧条目

        for neighbour, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbour]:
                dist[neighbour] = new_dist
                heapq.heappush(heap, (new_dist, neighbour))

    return dist
​

• 用二叉堆时时间：O((|V| + |E|) \log |V|)。

• 陷阱：if d > dist[node]: continue 这一行必不可少。没有它，你会处理陈旧的堆条目，可能退化到 O(|V|^2)。

• 陷阱：Dijkstra 不能处理负权边。如果某条边是负权，「一旦节点敲定其距离就最优」这个贪心假设就会失效。改用 Bellman-Ford。

困难：网络延迟时间

• 题目：给定 n 个节点和带权有向边，求信号从源点传到所有节点所需的时间。若并非所有节点都可达则返回 -1。

def network_delay(times, n, k):
    graph = {i: [] for i in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))

    dist = dijkstra(graph, k)
    max_time = max(dist.values())
    return max_time if max_time < float('inf') else -1
​

强连通分量

• 在有向图中，**强连通分量（strongly connected component，SCC）**是一个极大的节点集合，其中每个节点都能到达其他所有节点。

• Kosaraju 算法：(1) 在原图上做 DFS，记录完成顺序。(2) 转置图（反转所有边）。(3) 按完成顺序的逆序在转置图上做 DFS。第 3 步的每棵 DFS 树就是一个 SCC。

• 何时使用：找循环依赖、2-SAT、把有向图凝聚成一个由 SCC 组成的 DAG。

常见陷阱汇总

编程练习（使用 CoLab 或 notebook）

以下题目可在 NeetCode 的题目列表中练习。

BFS 模式

• Number of Islands（岛屿数量）—— 网格 BFS/DFS
• Rotting Oranges（腐烂的橘子）—— 多源 BFS
• Clone Graph（克隆图）—— BFS + 哈希表克隆
• Pacific Atlantic Water Flow（太平洋大西洋水流）—— 从两侧海域分别 BFS
• Word Ladder（单词接龙）—— 隐式图上的 BFS

DFS 模式

• Max Area of Island（岛屿的最大面积）—— 带面积计数的 DFS
• Course Schedule（课程表）—— 有向图环检测
• Course Schedule II（课程表 II）—— 拓扑排序
• Number of Connected Components（连通分量数）—— DFS 或并查集
• Graph Valid Tree（有效的图树）—— 连通 + 无环

最短路径

• Network Delay Time（网络延迟时间）—— Dijkstra
• Cheapest Flights Within K Stops（K 站中转内最便宜的航班）—— 带约束的改进 BFS/Bellman-Ford
• Swim in Rising Water（水位上升的泳池中游泳）—— 二分查找 + BFS 或网格上的 Dijkstra

进阶

• Alien Dictionary（外星人字典）—— 从字符顺序做拓扑排序