第7章图 — 算法与数据结构

图的基本概念

顶点（Vertex）图的基本单元，也叫节点
边（Edge）连接两个顶点的关系；有向图区分起点和终点
权重（Weight）边上的数值，如距离、代价、时间
度（Degree）连接到某顶点的边数；有向图分入度和出度
路径（Path）从一个顶点到另一个顶点经过的顶点序列
连通性无向图中任意两点间存在路径，则称图是连通的
DAG有向无环图（Directed Acyclic Graph），拓扑排序的基础

图的表示

邻接矩阵

matrix[i][j] = 1（或权重）表示顶点 i 到顶点 j 有边。

# 邻接矩阵表示 5 个顶点的无向图
n = 5
matrix = [[0] * n for _ in range(n)]
# 添加边 0-1, 1-2, 2-3, 3-4
for u, v in [(0,1),(1,2),(2,3),(3,4)]:
    matrix[u][v] = matrix[v][u] = 1  # 无向图，对称

# 查询 u-v 是否有边：O(1)
# 获取 u 的所有邻居：O(n)（需遍历整行）
# 空间：O(n²) — 稠密图合适，稀疏图浪费

邻接表

from collections import defaultdict

# 邻接表：每个顶点维护其邻居列表
graph = defaultdict(list)
for u, v in [(0,1),(1,2),(2,3),(3,4)]:
    graph[u].append(v)
    graph[v].append(u)  # 无向图

# 带权重的邻接表
weighted_graph = defaultdict(list)
for u, v, w in [(0,1,4),(1,2,3),(2,3,1)]:
    weighted_graph[u].append((v, w))  # (邻居, 权重)

# 获取 u 的所有邻居：O(度数)  — 稀疏图高效
# 空间：O(V + E)

对比	邻接矩阵	邻接表
空间	O(V²)	O(V + E)
判断边是否存在	O(1)	O(度数)
遍历所有邻居	O(V)	O(度数)
适用	稠密图（E ≈ V²）	稀疏图（E << V²）

深度优先搜索（DFS）

DFS 沿着一条路径尽可能深地搜索，直到无法继续为止，然后回溯到上一个节点尝试其他路径。

# 递归 DFS
def dfs_recursive(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)   # 处理当前节点
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# 迭代 DFS（用显式栈）
def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                stack.append(neighbor)

DFS 时间O(V + E) DFS 空间O(V)

广度优先搜索（BFS）

BFS 按层次由近及远搜索，用队列维护待访问节点。在无权图中，BFS 找到的是最短路径（最少边数）。

from collections import deque

def bfs_shortest_path(graph, start, end):
    """无权图最短路径（边数最少）"""
    if start == end:
        return [start]
    queue = deque([(start, [start])])   # (节点, 路径)
    visited = {start}

    while queue:
        node, path = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                new_path = path + [neighbor]
                if neighbor == end:
                    return new_path   # BFS 第一次到达即最短路径
                visited.add(neighbor)
                queue.append((neighbor, new_path))
    return []  # 不可达

拓扑排序

拓扑排序将 DAG 的所有顶点排成线性序列，使得对每条有向边 (u, v)，顶点 u 在 v 之前。应用场景：课程表、任务依赖、编译依赖。

Kahn 算法（BFS 实现）

from collections import deque, defaultdict

def topological_sort_kahn(n, prerequisites):
    """
    n: 顶点数 (0 到 n-1)
    prerequisites: [[a, b], ...] 表示 b → a 的有向边（b 必须在 a 之前）
    """
    graph = defaultdict(list)
    in_degree = [0] * n

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

    # 将所有入度为 0 的节点加入队列
    queue = deque([i for i in range(n) if in_degree[i] == 0])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)   # 入度降为 0，可以访问

    if len(order) == n:
        return order   # 成功，返回拓扑序
    return []          # 有环，无法拓扑排序

💡

判断有环若拓扑排序后，输出节点数 < 总节点数，说明存在环（部分节点的入度永远不会降为 0）。

Dijkstra 最短路径算法

Dijkstra 算法求有权图中从源点到所有其他顶点的最短路径。使用贪心策略：每次从未确定的节点中选距离最短的，保证其已找到最短路径。

⚠️

前提Dijkstra 仅适用于非负权重的图。负权重需用 Bellman-Ford 算法。

import heapq

def dijkstra(graph, start):
    """
    graph: {节点: [(邻居, 权重), ...]}
    返回: dist 字典，dist[v] = 从 start 到 v 的最短距离
    """
    dist = defaultdict(lambda: float('inf'))
    dist[start] = 0
    heap = [(0, start)]   # (距离, 节点)，最小堆

    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:    # 过时的记录，跳过
            continue
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))

    return dist

# 示例
g = defaultdict(list)
for u, v, w in [(0,1,4),(0,2,1),(2,1,2),(1,3,1),(2,3,5)]:
    g[u].append((v, w))
print(dijkstra(g, 0))
# {0: 0, 2: 1, 1: 3, 3: 4}  ← 0→2→1→3 = 1+2+1 = 4

Dijkstra（堆优化）O((V+E) log V)

并查集（Union-Find）

并查集高效地维护"哪些节点属于同一个连通分量"的信息，支持两种操作：

find(x)：找到 x 所在连通分量的代表（根节点）
union(x, y)：合并 x 和 y 所在的两个连通分量

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 初始每个节点自己是根
        self.rank = [0] * n            # 树的秩（近似高度）
        self.count = 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) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False   # 已连通
        # 按秩合并：小树挂在大树下
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

    def connected(self, x, y) -> bool:
        return self.find(x) == self.find(y)

find / union接近 O(1)

精确地说是 O(α(n))，其中 α 是反阿克曼函数，对所有实际问题的 n 均 ≤ 4。

经典题目

岛屿数量（DFS/BFS 连通分量）

def num_islands(grid) -> int:
    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] != '1':
            return
        grid[r][c] = '0'  # 标记为已访问（原地修改）
        for dr, dc in [(+1,0),(-1,0),(0,+1),(0,-1)]:
            dfs(r+dr, c+dc)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)   # 将整个岛屿淹没
                count += 1
    return count

课程表（拓扑排序判断是否可以完成）

def can_finish(n, prerequisites) -> bool:
    order = topological_sort_kahn(n, prerequisites)
    return len(order) == n   # 能完成所有课程 ↔ 没有环

Floyd-Warshall 全源最短路

Floyd-Warshall 算法求所有顶点对之间的最短路径，允许负权重（但不能有负权环）。

核心思想：动态规划。dp[k][i][j] 表示只经过顶点 0..k 作为中间节点时，i 到 j 的最短路径。转移方程：dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])，即"经过 k" vs "不经过 k"。

def floyd_warshall(n: int, edges: list) -> list:
    """
    n: 顶点数
    edges: [(u, v, w), ...] 有向带权边
    返回: dist[i][j] = i 到 j 的最短路径，不可达为 inf
    """
    INF = float('inf')
    # 初始化距离矩阵
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0   # 自身到自身距离为 0
    for u, v, w in edges:
        dist[u][v] = min(dist[u][v], w)  # 可能有重边

    # 枚举中间节点 k
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # 经过 k 是否更短？
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # 检测负权环：对角线元素 < 0 说明存在负权环
    for i in range(n):
        if dist[i][i] < 0:
            raise ValueError("负权环存在，最短路无意义")

    return dist

# 时间 O(V³)，空间 O(V²)
# 适用：顶点数较少（V ≤ 500），需要所有顶点对间的最短路

Bellman-Ford 算法（含负权）

处理含负权边的单源最短路径，时间 O(VE)。核心：对所有边进行 V-1 轮松弛，第 V 轮若还能松弛则说明存在负权环。

def bellman_ford(n, edges, start):
    """edges: [(u, v, w), ...] 可以包含负权"""
    INF = float('inf')
    dist = [INF] * n
    dist[start] = 0

    # 进行 n-1 轮松弛
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    # 第 n 轮若仍能松弛，则存在负权环
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return None   # 有负权环

    return dist
# 时间 O(VE)，慢于 Dijkstra，但能处理负权边

✅

图算法选型
连通性/遍历 → DFS 或 BFS（O(V+E)）
无权图最短路径（边数）→ BFS
有权图单源最短路（非负权）→ Dijkstra O((V+E) log V)
有权图单源最短路（含负权）→ Bellman-Ford O(VE)
全源最短路 → Floyd-Warshall O(V³)（V 较小时）
连通分量（动态合并）→ 并查集（接近 O(1)）
有向图环检测/任务排序 → 拓扑排序（Kahn BFS）O(V+E)

📌

本章小结
图是最通用的数据结构，现实世界中大量问题本质上都是图问题：地图导航（最短路）、社交网络（连通分量）、课程表（拓扑排序）、网络流（最大流）。

存储选择：稀疏图用邻接表 O(V+E)，稠密图用邻接矩阵 O(V²)。

算法速查：DFS/BFS 遍历 → 拓扑排序检测环 → Dijkstra 非负权单源 → Bellman-Ford 含负权单源 → Floyd-Warshall 全源 → 并查集动态连通性。

并查集的路径压缩 + 按秩合并使得 find/union 摊还时间接近 O(1)（精确为反阿克曼函数 α(n) ≤ 4）。