图

本章目标：掌握图的表示与遍历，能解决拓扑排序、最短路径、最小生成树等经典问题。

你将学到

• 邻接矩阵与邻接表
• BFS 与 DFS 图遍历
• 连通分量计数
• 拓扑排序（Kahn 算法 / DFS）
• 最短路径（Dijkstra、Bellman-Ford、Floyd）
• 最小生成树（Prim、Kruskal）

1. 概念

图由顶点（Vertex）和边（Edge）组成。根据边是否有方向，分为有向图和无向图；根据边是否有权重，分为加权图和非加权图。

两种主流表示方式：

• 邻接矩阵：graph[i][j] 表示 i 到 j 的边，空间 O(V²)，适合稠密图
• 邻接表：每个顶点存一个链表/数组，空间 O(V+E)，适合稀疏图

图论问题的通用思路：先想清楚遍历方式（BFS 还是 DFS），再加额外状态记录。

2. 核心模板

BFS 遍历（找最短步数）

from collections import deque

def bfs(graph, start):
    """BFS 遍历，返回到每个节点的最短步数"""
    visited = set([start])
    queue = deque([(start, 0)])  # (节点, 步数)
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return visited

DFS 遍历

def dfs(graph, node, visited):
    """DFS 递归遍历"""
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

拓扑排序（Kahn 算法）

from collections import deque

def topologicalSort(numCourses, prerequisites):
    """返回拓扑排序结果，如果存在环则返回空列表"""
    graph = [[] for _ in range(numCourses)]
    inDegree = [0] * numCourses
    for dst, src in prerequisites:
        graph[src].append(dst)
        inDegree[dst] += 1

    queue = deque([i for i in range(numCourses) if inDegree[i] == 0])
    result = []
    while queue:
        node = queue.popleft()
        result.append(node)
        for neighbor in graph[node]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.append(neighbor)

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

Dijkstra 最短路径

import heapq

def dijkstra(graph, start, n):
    """单源最短路径，graph[u] = [(v, w), ...]"""
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]  # (距离, 节点)
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue  # 已有更优解
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

复杂度

• BFS/DFS：时间 O(V + E)，空间 O(V)
• 拓扑排序：时间 O(V + E)
• Dijkstra（堆优化）：时间 O((V + E) log V)

3. 经典题目精讲

LeetCode 200 · 岛屿数量

题意：给定二维网格，'1' 为陆地，'0' 为水，求岛屿数量。

思路：遍历每个格子，遇到 '1' 就 DFS/BFS 把整个连通区域标记为已访问，岛屿数 +1。

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # 标记已访问
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

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

LeetCode 207 · 课程表

题意：判断是否可以完成所有课程（有向图是否有环）。

思路：拓扑排序，如果结果包含所有课程则无环。

def canFinish(numCourses, prerequisites):
    from collections import deque
    graph = [[] for _ in range(numCourses)]
    inDegree = [0] * numCourses
    for dst, src in prerequisites:
        graph[src].append(dst)
        inDegree[dst] += 1

    queue = deque([i for i in range(numCourses) if inDegree[i] == 0])
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for neighbor in graph[node]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.append(neighbor)
    return count == numCourses

4. 易错点

• ⚠️ 无向图每条边存两次（u→v 和 v→u），遍历时注意去重
• ⚠️ BFS 用 deque.popleft() 是 O(1)，list.pop(0) 是 O(n)
• ⚠️ Dijkstra 不适用于负权边，有负权用 Bellman-Ford
• ⚠️ 修改网格/矩阵做标记时，确认原数据可以修改

5. 推荐刷题清单

题号	题名	难度	关键
200	岛屿数量	Medium	DFS/BFS
207	课程表	Medium	拓扑排序
210	课程表 II	Medium	拓扑排序
329	矩阵中的最长递增路径	Hard	记忆化+DFS
743	网络延迟时间	Medium	Dijkstra
787	K 站中转内最便宜的航班	Medium	Bellman-Ford

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS) 第 22-26 章