图：基础与遍历

第 10 章 · 数据结构与算法

从点到线，从树到图。 前面学的树是「一个根、层层分叉、没有环」的特殊结构。若允许节点之间任意相连、甚至形成环，就得到图（graph）：由顶点（vertex）和边（edge）组成，可表示社交网络、路网、依赖关系等。图的遍历是很多算法的基础：深度优先（DFS）像「一条路走到底再回溯」，广度优先（BFS）像「一圈圈往外扩」。本章讲图的基本概念、邻接表与邻接矩阵、DFS 与 BFS 的递归与迭代实现，并配有示意图、Python 代码（类型标注与注释）以及至少三道例题。

一、图的基本概念

图 G = (V, E) 由顶点集 V 和边集 E 组成。一条边连接两个顶点；若边有方向则称有向图，否则为无向图。无向图可视为「每条边都是双向」的有向图。边上可带权（长度、代价），称为带权图。

度：无向图中顶点的度指与之相连的边数；有向图分入度（指向该顶点的边数）和出度（从该顶点指出的边数）。路径是顶点序列，相邻顶点之间有边；若路径不重复经过顶点则称简单路径。环是首尾相同的路径。无向图中若任意两顶点间都存在路径，则称图连通；有向图中若任意两顶点互相可达，则称强连通。

无向图：四个顶点、五条边，形成环 A-B-C-D-A 及 A-C

二、图的存储

常见两种表示：邻接表（adjacency list）为每个顶点维护一个列表，存其所有邻接点（或出边），适合稀疏图，遍历邻接点 O(度)；邻接矩阵（adjacency matrix）为 n×n 矩阵，adj[i][j] 表示 i→j 是否有边（或边权），适合稠密图或需 O(1) 查两点是否相邻时。

邻接表：顶点 0 的邻居为 1、2；顶点 2 的邻居为 0、1、3

from typing import List


def build_adj_list(n: int, edges: List[List[int]], directed: bool = False) -> List[List[int]]:
    """
    建无向或有向图的邻接表。n 为顶点数（顶点编号 0..n-1），
    edges 为边列表，每条边 [u, v] 表示 u→v（有向）或 u-v（无向）。
    """
    adj: List[List[int]] = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        if not directed:
            adj[v].append(u)
    return adj


def build_adj_matrix(n: int, edges: List[List[int]], directed: bool = False) -> List[List[int]]:
    """
    建邻接矩阵，adj[i][j]=1 表示有边，0 表示无。带权图可存权值代替 1。
    """
    adj: List[List[int]] = [[0] * n for _ in range(n)]
    for u, v in edges:
        adj[u][v] = 1
        if not directed:
            adj[v][u] = 1
    return adj

三、深度优先遍历（DFS）

深度优先（Depth-First Search）：从某顶点出发，沿一条路一直走到底（递归或显式栈），再回溯到上一个分支点走另一条路，直到所有可达顶点被访问。递归实现简洁；显式栈可避免递归深度过大。需要「已访问」标记避免重复。时间 O(V+E)（邻接表），空间 O(V)。

DFS：先深入一条路径，再回溯

from typing import List, Callable


def dfs_recursive(
    adj: List[List[int]],
    start: int,
    visited: List[bool],
    on_visit: Callable[[int], None],
) -> None:
    """
    从 start 开始递归 DFS。visited 在外部维护，避免重复访问；
    on_visit(u) 在首次访问顶点 u 时调用（可用来收集顺序或处理节点）。
    """
    visited[start] = True
    on_visit(start)
    for v in adj[start]:
        if not visited[v]:
            dfs_recursive(adj, v, visited, on_visit)


def dfs_iterative(adj: List[List[int]], start: int) -> List[int]:
    """
    用显式栈实现 DFS，返回从 start 出发的访问顺序。
    """
    order: List[int] = []
    visited: List[bool] = [False] * len(adj)
    stack: List[int] = [start]
    while stack:
        u = stack.pop()
        if visited[u]:
            continue
        visited[u] = True
        order.append(u)
        for v in reversed(adj[u]):  # 反转使顺序与递归版一致（先压的后弹）
            if not visited[v]:
                stack.append(v)
    return order

四、广度优先遍历（BFS）

广度优先（Breadth-First Search）：从某顶点出发，先访问其所有直接邻居，再访问邻居的邻居，层层外扩。用队列实现：将起点入队，每次出队一个顶点并访问，将其未访问的邻居入队。BFS 保证「先被访问的顶点距离更近」，因此可求无权图最短路径（步数）。时间 O(V+E)，空间 O(V)。

BFS：按层扩散，适合求最短步数

from collections import deque
from typing import List


def bfs(adj: List[List[int]], start: int) -> List[int]:
    """
    从 start 开始 BFS，返回访问顺序。用队列保证「先被发现的先扩展」。
    """
    order: List[int] = []
    visited: List[bool] = [False] * len(adj)
    q: deque = deque([start])
    visited[start] = True
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                q.append(v)
    return order


def bfs_shortest_distances(adj: List[List[int]], start: int) -> List[int]:
    """
    无权图下从 start 到各点的最短距离（边数）。
    不可达顶点距离为 -1 或 inf。在 BFS 时记录层数即可。
    """
    n = len(adj)
    dist: List[int] = [-1] * n
    dist[start] = 0
    q: deque = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

五、DFS 与 BFS 对比与应用

DFS 适合：遍历所有顶点、找连通分量、检测环、拓扑排序、回溯枚举。BFS 适合：无权最短路径、层序遍历、按距离分层。二者时间均为 O(V+E)（邻接表），空间 O(V)。多源 BFS：多个起点同时入队，可求「到任意起点最近」的距离。

对比	DFS	BFS
实现	递归或栈	队列
顺序	一条路走到底再回溯	按层、由近及远
最短路径（无权）	需额外记录	天然得到
典型应用	连通分量、环、拓扑、回溯	最短步数、层序、多源扩散

DFS 与 BFS 对比

小贴士： 图不连通时，需对每个未访问顶点作为起点做一次 DFS/BFS，才能遍历全图或统计连通分量。

六、小结

图由顶点与边组成，分有向/无向、带权/无权。邻接表省空间、适合遍历；邻接矩阵适合稠密或 O(1) 查边。DFS 用递归或栈，一条路走到底；BFS 用队列，按层扩散，可求无权最短路径。下一章讲图算法：最短路、最小生成树等。

七、例题

以下例题使用 Python 3 类型标注与注释；图以邻接表或二维网格表示。

例题 1：岛屿数量

题目描述：给定二维网格 grid，'1' 表示陆地，'0' 表示水。水平或竖直相邻的 '1' 视为同一块陆地。求岛屿数量（连通块数）。

输入：grid 为 m×n 的字符矩阵。
输出：岛屿个数。

from typing import List


def num_islands(grid: List[List[str]]) -> int:
    """
    对每个未访问的 '1' 做一次 DFS 或 BFS，标记整块陆地，计数即岛屿数。
    原地用 '0' 或额外 visited 标记已访问。
    """
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(i: int, j: int) -> None:
        if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] != '1':
            return
        grid[i][j] = '0'
        dfs(i - 1, j)
        dfs(i + 1, j)
        dfs(i, j - 1)
        dfs(i, j + 1)

    count = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

讲解：网格可视为图：每个格子是顶点，上下左右相邻的 '1' 之间有边。求连通分量数：遍历格子，遇到 '1' 就做一次 DFS 把整块陆地标记掉（改为 '0'），计数。时间 O(m×n)，空间 O(m×n) 递归栈（可改为 BFS+队列）。

例题 2：克隆图

题目描述：给定无向连通图的一个节点 node，每个节点含 val 与 neighbors（邻居列表）。深拷贝整张图，返回克隆后的对应节点。

思路：DFS 或 BFS 遍历原图，用哈希表记录「原节点 → 克隆节点」，遍历到邻居时若未克隆则先克隆再连边。

from typing import Optional, List


class Node:
    def __init__(self, val: int = 0, neighbors: Optional[List["Node"]] = None) -> None:
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


def clone_graph(node: Optional[Node]) -> Optional[Node]:
    if node is None:
        return None
    clone_map: dict = {}  # 原节点 -> 克隆节点

    def dfs(u: Node) -> Node:
        if u in clone_map:
            return clone_map[u]
        c = Node(u.val)
        clone_map[u] = c
        for v in u.neighbors:
            c.neighbors.append(dfs(v))
        return c

    return dfs(node)

讲解：DFS 进入某节点时，若已克隆过则直接返回克隆节点（避免环死循环）；否则创建克隆、存入 map、递归克隆所有邻居并接到克隆的 neighbors。时间 O(V+E)，空间 O(V)。

例题 3：课程表（拓扑排序）

题目描述：共有 numCourses 门课，编号 0..numCourses-1。给定前置关系 prerequisites[i]=[a,b] 表示修 a 前需先修 b（即 a 依赖 b）。判断能否完成所有课程（图是否有环）。

输入：numCourses 与边列表。
输出：True 表示可以完成，False 表示存在环。

from typing import List


def can_finish(num_courses: int, prerequisites: List[List[int]]) -> bool:
    """
    建图：b -> a 表示修 a 前需修 b（即 a 依赖 b）。能完成等价于有向图无环。
    用 DFS 检测环：维护「正在访问」集合，若 DFS 时遇到正在访问的节点则有环。
    或用 Kahn 拓扑：入度为 0 的依次出队，若最后出队数 < 顶点数则有环。
    """
    adj: List[List[int]] = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        adj[b].append(a)  # 边 b -> a：修 a 前需修 b，即 b 是 a 的前置

    state: List[int] = [0] * num_courses  # 0 未访问 1 正在访问 2 已结束

    def has_cycle(u: int) -> bool:
        state[u] = 1
        for v in adj[u]:
            if state[v] == 1:
                return True
            if state[v] == 0 and has_cycle(v):
                return True
        state[u] = 2
        return False

    for i in range(num_courses):
        if state[i] == 0 and has_cycle(i):
            return False
    return True

讲解：依赖关系构成有向图；能完成所有课当且仅当图无环。DFS 时用三色：未访问(0)、正在递归中(1)、已结束(2)。若在递归中再次遇到状态为 1 的节点，说明存在反向边即环。时间 O(V+E)，空间 O(V)。

例题 4：腐烂的橘子（多源 BFS）

题目描述：网格中 2 表示腐烂橘子，1 表示新鲜，0 表示空。每分钟与腐烂相邻的新鲜会变腐烂。问多少分钟后没有新鲜橘子；若不可能则返回 -1。

思路：所有 2 作为起点同时入队，做 BFS，记录每格被感染的时间（步数）。最后若仍有 1 则 -1，否则为最大步数。

from collections import deque
from typing import List


def oranges_rotting(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    q: deque = deque()
    fresh = 0
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 2:
                q.append((i, j, 0))
            elif grid[i][j] == 1:
                fresh += 1
    if fresh == 0:
        return 0
    dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_minutes = 0
    while q:
        i, j, minutes = q.popleft()
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
                grid[ni][nj] = 2
                fresh -= 1
                max_minutes = max(max_minutes, minutes + 1)
                q.append((ni, nj, minutes + 1))
    return max_minutes if fresh == 0 else -1

讲解：多源 BFS：所有 2 的 (i, j, 0) 入队，每次扩展四邻 1 并标记为 2、记录分钟数。若 BFS 结束后仍有 fresh 则返回 -1。时间 O(m×n)，空间 O(m×n)。