图

图的基本概念

• 顶点（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 []          # 有环，无法拓扑排序

Dijkstra 最短路径算法

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

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   # 能完成所有课程 ↔ 没有环