30 秒速览

  • 什么时候用：关系网络、路径问题、连通性、依赖关系
  • 核心操作：遍历、拓扑排序、并查集、最短路径
  • 存储方式：邻接矩阵 vs 邻接表
  • 遍历方式：DFS（递归/栈）、BFS（队列）

一、直觉建立

什么是图？

图由**顶点（Vertex）和边（Edge）**组成，表示事物之间的关系。

    A --- B
    |     |
    C --- D

顶点：A, B, C, D
边：(A,B), (A,C), (B,D), (C,D)

图的分类

类型特点例子
无向图边无方向社交网络
有向图边有方向网页链接
有权图边有权重地图导航
无权图边无权重连通性

图的存储

邻接矩阵：

# matrix[i][j] = 1 表示 i 和 j 相连
matrix = [
    [0, 1, 1, 0],  # A
    [1, 0, 0, 1],  # B
    [1, 0, 0, 1],  # C
    [0, 1, 1, 0],  # D
]

邻接表：

# graph[i] = [相邻节点列表]
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C'],
}
方式空间适用场景
邻接矩阵O(V²)稠密图、频繁查边
邻接表O(V+E)稀疏图、遍历操作

二、图的遍历

DFS 模板

def dfs(graph, start, visited):
    visited.add(start)

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

BFS 模板

from collections import deque

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

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

标记时机的区别

# 方式 1：入队时标记（推荐）
queue.append(start)
visited.add(start)

# 方式 2：出队时标记（可能重复入队）
queue.append(start)
while queue:
    node = queue.popleft()
    visited.add(node)  # 太晚了

三、典型例题

例题 1：LC 200. 岛屿数量

题目：给定一个由 ‘1’（陆地）和 ‘0’（水）组成的二维网格，计算岛屿数量。

思路

网格可以看作图，每个格子是顶点，上下左右是边。

DFS 实现：

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
            return

        grid[i][j] = '0'  # 标记为已访问

        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)

    return count

复杂度：时间 O(mn)，空间 O(mn)（递归栈）

例题 2：LC 207. 课程表

题目：给定课程数量和先修关系，判断是否能完成所有课程。

示例：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true（先修课程 0，再修课程 1）

拓扑排序

这是经典的拓扑排序问题，本质是检测有向图是否有环。

BFS（Kahn 算法）：

from collections import deque, defaultdict

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    # 构建邻接表和入度数组
    graph = defaultdict(list)
    in_degree = [0] * numCourses

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

    # 入度为 0 的课程入队
    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0

    while queue:
        course = queue.popleft()
        count += 1

        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return count == numCourses

复杂度：时间 O(V+E)，空间 O(V+E)

DFS 检测环：

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = defaultdict(list)
    for course, prereq in prerequisites:
        graph[prereq].append(course)

    # 0: 未访问, 1: 访问中, 2: 已完成
    state = [0] * numCourses

    def has_cycle(course):
        if state[course] == 1:  # 发现环
            return True
        if state[course] == 2:  # 已处理
            return False

        state[course] = 1  # 标记为访问中

        for neighbor in graph[course]:
            if has_cycle(neighbor):
                return True

        state[course] = 2  # 标记为已完成
        return False

    for i in range(numCourses):
        if has_cycle(i):
            return False

    return True

例题 3：LC 210. 课程表 II

题目：返回完成所有课程的学习顺序。

from collections import deque, defaultdict

def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    graph = defaultdict(list)
    in_degree = [0] * numCourses

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

    queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
    result = []

    while queue:
        course = queue.popleft()
        result.append(course)

        for neighbor in graph[course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return result if len(result) == numCourses else []

例题 4：LC 547. 省份数量

题目：给定 n 个城市的连接矩阵，返回省份数量（连通分量数）。

def findCircleNum(isConnected: list[list[int]]) -> int:
    n = len(isConnected)
    visited = [False] * n
    count = 0

    def dfs(city):
        visited[city] = True
        for j in range(n):
            if isConnected[city][j] == 1 and not visited[j]:
                dfs(j)

    for i in range(n):
        if not visited[i]:
            count += 1
            dfs(i)

    return count

例题 5：LC 684. 冗余连接

题目：在无向图中找出一条可以删除的边，使图成为树。

并查集

并查集用于处理连通性问题，支持两种操作：

  • find(x)：找 x 的根
  • union(x, y)：合并 x 和 y 所在的集合
def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    parent = list(range(len(edges) + 1))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # 路径压缩
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False  # 已经连通
        parent[px] = py
        return True

    for x, y in edges:
        if not union(x, y):
            return [x, y]

    return []

并查集优化：

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n  # 按秩合并

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False

        # 按秩合并
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

        return True

例题 6：LC 994. 腐烂的橘子

题目：网格中的橘子，每分钟腐烂的橘子会感染相邻的新鲜橘子，求所有橘子腐烂的最少分钟数。

多源 BFS

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    # 初始化：所有腐烂橘子入队
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1

    if fresh == 0:
        return 0

    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    minutes = 0

    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()

            for dx, dy in directions:
                nx, ny = x + dx, y + dy

                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh -= 1
                    queue.append((nx, ny))

    return minutes if fresh == 0 else -1

复杂度：时间 O(mn)，空间 O(mn)

四、图问题分类

问题类型核心算法典型题目
连通性DFS/BFS/并查集岛屿数量、省份数量
拓扑排序Kahn/DFS课程表
环检测DFS 三色/并查集课程表、冗余连接
最短路径BFS/Dijkstra单词接龙
最小生成树Kruskal/Prim连接所有点

五、常见错误与陷阱

错误 1：忘记标记已访问

# 错误：死循环
def dfs(node):
    for neighbor in graph[node]:
        dfs(neighbor)  # 无限递归

# 正确
def dfs(node):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor)

错误 2：BFS 标记时机

# 错误：出队时标记，可能重复入队
while queue:
    node = queue.popleft()
    visited.add(node)  # 太晚

# 正确：入队时标记
visited.add(start)
queue.append(start)
while queue:
    ...

错误 3：并查集忘记路径压缩

# 未优化：可能退化成链表
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

# 优化：路径压缩
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

错误 4：有向图环检测状态错误

# 三种状态
# 0: 未访问
# 1: 正在访问（当前路径上）
# 2: 已完成

# 只有状态 1 -> 1 才是环

六、复盘清单

触发信号

  • 关系网络
  • 连通性判断
  • 依赖关系/先修条件
  • 最短路径
  • 环检测

算法选择

  • 连通分量 → DFS/BFS/并查集
  • 依赖关系 → 拓扑排序
  • 动态连通性 → 并查集
  • 最短路径（无权）→ BFS
  • 最短路径（有权）→ Dijkstra

边界条件

  • 空图
  • 单节点
  • 全连通
  • 有环/无环

七、题目清单

基础题

题号题目难度考点
200岛屿数量MediumDFS/BFS
547省份数量MediumDFS/并查集
207课程表Medium拓扑排序
994腐烂的橘子Medium多源 BFS

进阶题

题号题目难度考点
210课程表 IIMedium拓扑排序
684冗余连接Medium并查集
133克隆图Medium图复制
127单词接龙HardBFS
743网络延迟时间MediumDijkstra