Skip to content

图

图用于建模关系和连接，从社交网络到道路地图再到依赖链。本篇将介绍图的表示方法、BFS、DFS、最短路径、拓扑排序和连通分量，重点讲解图面试题中占主导地位的遍历和寻路模式。

  • 我们在第12章（邻接矩阵、拉普拉斯矩阵、谱性质）和第13章（树、平面性、图着色）中已经介绍了图论。这里我们专注于算法模式：如何在代码中遍历、搜索和优化图。

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

图的表示

  • 邻接表：对每个节点，存储一个其邻居的列表。空间复杂度：\(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

  • 邻接矩阵：\(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'（水域）组成的二维网格，计算岛屿的数量。

  • 模式：遍历网格。当遇到 '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)] 这种处理四连通网格邻居的模式在几乎所有网格问题中都会用到。记住它。对于八连通，加上对角线方向。

  • 陷阱：修改输入网格（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（拓扑排序）

  • 问题：返回一个有效的课程顺序（拓扑序）。

  • 模式（卡恩算法 — 基于 BFS）：从没有入边的节点（入度为 0）开始。处理它们，将邻居的入度减 1。重复此过程。

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: {node: [(neighbour, weight), ...]}
    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

强连通分量

  • 在有向图中，强连通分量（SCC） 是一个最大的节点集合，其中任意两个节点都可以互相到达。

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

  • 何时使用：寻找循环依赖、2-SAT、将有向图压缩为 SCC 的 DAG。

常见陷阱总结

陷阱 示例 解决方法
在出队时标记已访问 同一节点被多次入队 在入队时标记已访问
有向图中使用两种状态 无法区分后向边和横向边 使用三种状态：未访问/进行中/已完成
Dijkstra 用于负权边 得到错误的最短路径 改用 Bellman-Ford
忘记 if d > dist[node]: continue 处理过时的堆条目 当前距离更差时始终跳过
网格边界检查 索引越界 0 <= nr < rows and 0 <= nc < cols
未处理 time=0 的边界情况 腐烂橘子：没有新鲜橘子 在 BFS 之前检查 fresh == 0
将有向图构建成无向图 先修关系是单向的 只在一个方向上添加边

课后练习（NeetCode）

BFS 模式

DFS 模式

最短路径

进阶