图（Graph）：关系网络的数学抽象

什么是图？

图是由顶点（Vertex/Node）和边（Edge）组成的非线性数据结构，用于表示实体及其之间的关系。形式化定义为：

G = (V, E)

其中V是顶点集合，E是边集合。

为什么图如此重要？

1. 建模复杂关系：社交网络、交通系统、知识图谱
2. 解决路径问题：导航、网络路由
3. 依赖分析：任务调度、编译顺序
4. 推荐系统：基于图神经网络
5. 生物信息学：蛋白质相互作用网络

基本概念与术语

图的基本要素

• 有向图/无向图：边是否有方向性
• 加权图/无权图：边是否带有权重值
• 连通图：任意两顶点间存在路径
• 完全图：每对顶点间都有边连接

1. 有向图 vs 无向图

2. 加权图 vs 无权图

3. 连通图 vs 非连通图

4. 完全图 (Complete Graph)

如何快速区分？

1. 看边是否有方向 → 有向/无向图
2. 看边是否有数字 → 加权/无权图
3. 任意两点能否互通 → 连通/非连通图
4. 是否所有点都互相直连 → 是否完全图

经典算法应用场景

• 有向加权图：Dijkstra找最短路径
• 无向无权图：BFS找社交关系中的朋友
• 非连通图：计算连通分量数量
• 完全图：验证图论定理（如边数公式）

特殊图类型

• 树：无环连通图（特殊的图）
• 二分图：顶点可分为两个不相交集合
• DAG（有向无环图）：无循环的有向图
• 欧拉图：包含欧拉回路的图
• 哈密顿图：包含哈密顿回路的图

核心区别总结

1. 树 vs 普通图

   • 树是无环连通图的特殊情况，普通图可能有环或不连通。

2. 二分图 vs 非二分图

   • 二分图可通过二着色测试验证（如用BFS），非二分图可能存在奇数环。

3. DAG vs 有环有向图

   • DAG可进行拓扑排序，而有环图无法排序（如A→B→C→A）。

4. 欧拉图 vs 哈密顿图

   • 欧拉图关注边遍历（边不重复），哈密顿图关注顶点遍历（顶点不重复）。

5. 欧拉图与哈密顿图的关系

   • 欧拉图不一定是哈密顿图，反之亦然。 示例：
     • 菱形图（A-B-C-D-A加上A-C）是哈密顿图但不是欧拉图（存在奇度顶点）。
     • 四边形环（A-B-C-D-A）既是欧拉图也是哈密顿图。

算法与判定方法

实际应用举例

1. 树：家族关系图谱、组织结构图。
2. 二分图：求职平台（求职者↔岗位）、电影推荐（用户↔电影）。
3. DAG：课程选修依赖关系、编译器的任务调度。
4. 欧拉图：垃圾回收车的路线规划（每条街道清扫一次）。
5. 哈密顿图：快递员的最短送货路线（每个地址访问一次）。

图的表示方法

1. 邻接矩阵

# 无向图邻接矩阵示例A  B  C  D
A [0, 1, 1, 0]
B [1, 0, 1, 1]
C [1, 1, 0, 0]
D [0, 1, 0, 0]

• 优点：快速判断两顶点是否相邻
• 缺点：空间复杂度O(V²)，稀疏图浪费空间

2. 邻接表

{'A': ['B', 'C'],'B': ['A', 'C', 'D'],'C': ['A', 'B'],'D': ['B']
}

• 优点：空间效率高O(V+E)，适合稀疏图
• 缺点：查询相邻关系稍慢

3. 边列表

[('A','B'), ('A','C'), ('B','C'), ('B','D')]

• 优点：简单直观，适合某些算法
• 缺点：查询效率低

图的基本操作实现

Python图类实现（邻接表）

class Graph:def __init__(self, directed=False):self.graph = {}  # 邻接表self.directed = directeddef add_vertex(self, vertex):if vertex not in self.graph:self.graph[vertex] = []def add_edge(self, v1, v2, weight=None):self.add_vertex(v1)self.add_vertex(v2)self.graph[v1].append((v2, weight))if not self.directed:self.graph[v2].append((v1, weight))def get_vertices(self):return list(self.graph.keys())def get_edges(self):edges = []for vertex in self.graph:for neighbor, weight in self.graph[vertex]:if (vertex, neighbor, weight) not in edges:edges.append((vertex, neighbor, weight))return edges

1. 类结构概述

class Graph:def __init__(self, directed=False):self.graph = {}  # 邻接表self.directed = directed

• graph：用字典实现邻接表，存储顶点和边。
  • 键（Key）：顶点（如 'A'）
  • 值（Value）：邻接顶点列表，元素为元组 (邻居, 权重)（如 [('B', 3), ('C', 5)]）
• directed：标记是否为有向图（默认无向）。

2. 方法解析与图示

（1）添加顶点 add_vertex

def add_vertex(self, vertex):if vertex not in self.graph:self.graph[vertex] = []  # 初始化空邻接列表

操作示例：

g = Graph()
g.add_vertex('A')
g.add_vertex('B')

内存结构：

{'A': [],  # 顶点A暂无邻居'B': []   # 顶点B暂无邻居
}

（2）添加边 add_edge

def add_edge(self, v1, v2, weight=None):self.add_vertex(v1)self.add_vertex(v2)self.graph[v1].append((v2, weight))  # v1→v2if not self.directed:                # 无向图需双向添加self.graph[v2].append((v1, weight))

操作示例：

g = Graph(directed=False)
g.add_edge('A', 'B', weight=3)
g.add_edge('B', 'C', weight=2)

内存结构：

{'A': [('B', 3)],  # A ↔ B'B': [('A', 3), ('C', 2)],'C': [('B', 2)]
}

图示：

     3A ----- B/2 /C

（3）获取顶点 get_vertices

def get_vertices(self):return list(self.graph.keys())  # 返回所有顶点

示例输出：

['A', 'B', 'C']

（4）获取边 get_edges

def get_edges(self):edges = []for vertex in self.graph:for neighbor, weight in self.graph[vertex]:edges.append((vertex, neighbor, weight))return edges

示例输出：

[('A', 'B', 3), ('B', 'A', 3), ('B', 'C', 2), ('C', 'B', 2)]

3. 有向图 vs 无向图对比

无向图示例

g = Graph(directed=False)
g.add_edge('X', 'Y', 1)

内存结构：

{'X': [('Y', 1)],'Y': [('X', 1)]  # 自动反向添加
}

图示：

  X ——— Y

有向图示例

g = Graph(directed=True)
g.add_edge('X', 'Y', 1)

内存结构：

{'X': [('Y', 1)],'Y': []  # 无反向边
}

图示：

  X —→ Y

4. 完整测试案例

# 创建无向加权图
g = Graph(directed=False)
g.add_edge('A', 'B', 3)
g.add_edge('B', 'C', 2)
g.add_edge('A', 'C', 5)# 输出结果
print("顶点:", g.get_vertices())  # ['A', 'B', 'C']
print("边:", g.get_edges())      # [('A','B',3), ('B','A',3), ('B','C',2), ...]# 可视化结构
"""3A ----- B|     /
5 |   / 2| /C
"""

5. 关键点总结

1. 邻接表：用字典高效存储顶点和边。
2. 权重支持：边的权重通过元组 (邻居, 权重) 存储。
3. 方向控制：directed 参数决定是否自动添加反向边。
4. 动态扩展：添加边时会自动创建不存在的顶点。

图的遍历算法

深度优先搜索（DFS）

def dfs(graph, start, visited=None):if visited is None:visited = set()          # 初始化已访问集合visited.add(start)           # 标记当前节点为已访问print(start, end=' ')        # 输出访问的节点for neighbor, _ in graph[start]:  # 遍历邻居（忽略权重）if neighbor not in visited:dfs(graph, neighbor, visited)  # 递归访问未访问的邻居

1. 核心步骤图示

假设有以下无向图（邻接表表示）：

graph = {'A': [('B', 1), ('C', 1)],'B': [('A', 1), ('D', 1), ('E', 1)],'C': [('A', 1), ('F', 1)],'D': [('B', 1)],'E': [('B', 1), ('F', 1)],'F': [('C', 1), ('E', 1)]
}

图示：

      A/   \B     C/ \   /D   E-F

2. 执行过程分步演示

从起点 'A' 开始 DFS 的递归流程：

3. 关键点说明

1. 递归终止条件：当节点的所有邻居均被访问时，递归终止。
2. 回溯机制：通过递归调用栈自动实现回溯（如访问完 D 后回到 B）。
3. 避免重复访问：visited 集合确保每个节点只处理一次。
4. 忽略权重：代码中 for neighbor, _ in graph[start] 的 _ 表示忽略权重。

4. 输出结果

        执行 dfs(graph, 'A') 的输出结果为： A B D E F C

5. 对比 BFS 的访问顺序

        若使用广度优先搜索（BFS），同一图的访问顺序为： A B C D E F （使用队列按层遍历，与 DFS 的深入优先不同）

6. 常见问题解答

Q1: 如何处理有向图？

• 代码无需修改！邻接表已隐含方向性（例如 'A': [('B',1)] 表示 A→B）。

Q2: 如何记录访问路径而非仅输出节点？

• 修改代码为传递路径列表：

  def dfs_path(graph, start, path=None, visited=None):if visited is None:visited = set()if path is None:path = []visited.add(start)path.append(start)for neighbor, _ in graph[start]:if neighbor not in visited:dfs_path(graph, neighbor, path, visited)return path

输出：['A', 'B', 'D', 'E', 'F', 'C']

Q3: 非递归实现如何写？

• 使用栈模拟递归：

  def dfs_iterative(graph, start):visited = set()stack = [start]while stack:node = stack.pop()if node not in visited:print(node, end=' ')visited.add(node)for neighbor, _ in reversed(graph[node]):  # 保持顺序一致if neighbor not in visited:stack.append(neighbor)

广度优先搜索（BFS）

from collections import deque  # 使用双端队列实现高效队列def bfs(graph, start):visited = set()            # 记录已访问节点queue = deque([start])     # 初始化队列，从起点开始visited.add(start)         # 标记起点为已访问while queue:               # 当队列不为空时循环vertex = queue.popleft()  # 取出队列左侧节点（先进先出）print(vertex, end=' ') # 输出当前节点for neighbor, _ in graph[vertex]:  # 遍历当前节点的邻居（忽略权重）if neighbor not in visited:visited.add(neighbor)      # 标记邻居为已访问queue.append(neighbor)     # 将邻居加入队列

1. 核心步骤图示

假设有以下无向图（邻接表表示）：

graph = {'A': [('B', 1), ('C', 1)],'B': [('A', 1), ('D', 1), ('E', 1)],'C': [('A', 1), ('F', 1)],'D': [('B', 1)],'E': [('B', 1), ('F', 1)],'F': [('C', 1), ('E', 1)]
}

图示：

      A/   \B     C/ \   /D   E-F

2. 执行过程分步演示

从起点 'A' 开始 BFS 的流程：

3. 关键点说明

1. 队列的作用：确保按“先进先出”顺序访问节点，实现层级遍历。
2. visited 集合：防止重复访问（如 A-B-E-F-C 中 F 已被 E 加入队列，C 访问时不重复处理）。
3. 权重忽略：for neighbor, _ in graph[vertex] 中的 _ 表示忽略权重。
4. 与 DFS 的区别：
   • BFS 用队列，按层扩展；DFS 用栈/递归，深度优先。
   • 上例中 BFS 输出 A B C D E F，而 DFS 输出 A B D E F C。

4. 输出结果

执行 bfs(graph, 'A') 的输出结果为： A B C D E F

5. 应用场景

• 最短路径（无权图）：BFS 天然保证找到的路径是最短的。
• 社交网络好友推荐：按距离层级推荐朋友。
• 迷宫最短路径：从起点逐层探索可达位置。

6. 常见问题解答

Q1: 如何记录节点的层级？ 修改代码，在入队时保存层级：

def bfs_levels(graph, start):visited = {start: 0}  # 记录节点及其层级queue = deque([(start, 0)])  # (节点, 层级)while queue:vertex, level = queue.popleft()print(f"{vertex} (Level {level})")for neighbor, _ in graph[vertex]:if neighbor not in visited:visited[neighbor] = level + 1queue.append((neighbor, level + 1))

输出：

A (Level 0)
B (Level 1)
C (Level 1)
D (Level 2)
E (Level 2)
F (Level 2)

Q2: 如何实现有向图的 BFS？ 代码无需修改！邻接表已隐含方向性（如 'A': [('B',1)] 表示 A→B）。

Q3: 非连通图如何处理？ 对所有未访问的节点依次调用 BFS：

def bfs_all_components(graph):visited = set()for node in graph:if node not in visited:bfs(graph, node, visited)  # 需修改原函数支持传入visited

经典图算法

1. 最短路径

Dijkstra算法（非负权图）

import heapqdef dijkstra(graph, start):# 初始化所有节点距离为无穷大distances = {v: float('inf') for v in graph}distances[start] = 0  # 起点到自身的距离为0# 使用最小堆优先处理当前最短路径heap = [(0, start)]while heap:current_dist, current = heapq.heappop(heap)# 如果当前距离大于已知最短距离，跳过if current_dist > distances[current]:continue# 遍历邻居节点for neighbor, weight in graph[current]:distance = current_dist + weight# 发现更短路径时更新if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(heap, (distance, neighbor))return distances

1. 核心步骤图示

假设有以下有向加权图（邻接表表示）：

graph = {'A': [('B', 1), ('C', 4)],'B': [('C', 2), ('D', 5)],'C': [('D', 1)],'D': []
}

图示：

       A1/   \4B     C2/ \1  / D   E

2. 执行过程分步演示

从起点 'A' 计算最短路径：

最终结果：

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

3. 关键点说明

1. 最小堆的作用：始终优先处理当前距离起点最近的节点（贪心策略）。
2. 距离更新条件：仅当找到更短路径时更新并加入堆。
3. 跳过无效记录：if current_dist > distances[current]: continue 避免重复处理。
4. 时间复杂度：O((V+E) log V)，V为顶点数，E为边数。

4. 与 BFS 的区别

5. 应用场景

• 地图导航：计算两地间的最短行驶距离。
• 网络路由：寻找数据传输的最优路径。
• 任务调度：优化资源分配路径。

6. 常见问题解答

Q1: 如何处理负权边？ Dijkstra 无法处理负权边（可能导致无限循环），需改用 Bellman-Ford 算法。

Q2: 如何记录完整路径？ 添加 previous 字典记录前驱节点：

def dijkstra_with_path(graph, start):distances = {v: float('inf') for v in graph}previous = {v: None for v in graph}  # 新增distances[start] = 0heap = [(0, start)]while heap:current_dist, current = heapq.heappop(heap)if current_dist > distances[current]:continuefor neighbor, weight in graph[current]:distance = current_dist + weightif distance < distances[neighbor]:distances[neighbor] = distanceprevious[neighbor] = current  # 记录前驱节点heapq.heappush(heap, (distance, neighbor))return distances, previous

示例输出：

distances = {'A':0, 'B':1, 'C':3, 'D':4}
previous = {'A':None, 'B':'A', 'C':'B', 'D':'C'}
# 从D回溯路径：D→C→B→A

Q3: 为什么用堆而不用普通队列？ 堆能高效获取当前最小距离节点，确保每次处理的都是全局最优解。

Floyd-Warshall算法（所有顶点对）

def floyd_warshall(graph):vertices = list(graph.keys())  # 获取所有顶点n = len(vertices)# 初始化距离矩阵（n x n的二维数组）dist = [[float('inf')] * n for _ in range(n)]# 1. 初始化距离矩阵for i in range(n):dist[i][i] = 0  # 顶点到自身的距离为0for neighbor, weight in graph[vertices[i]]:j = vertices.index(neighbor)  # 找到邻居的索引dist[i][j] = weight  # 直接边的权重# 2. 动态规划求解所有顶点对的最短路径for k in range(n):          # 中间顶点for i in range(n):      # 起始顶点for j in range(n):  # 目标顶点# 如果通过k的路径更短，则更新if dist[i][j] > dist[i][k] + dist[k][j]:dist[i][j] = dist[i][k] + dist[k][j]# 3. 转换为字典形式返回结果return {v: dict(zip(vertices, row)) for v, row in zip(vertices, dist)}

1. 核心步骤图示

假设有以下有向加权图（允许负权边，但不含负权环）：

graph = {'A': [('B', 3), ('D', 7)],'B': [('A', 8), ('C', 2)],'C': [('D', 1), ('A', 5)],'D': [('B', 2)]
}

图示：

       A3↗↙8  ↘7B     D2↘  ↖2 ↗1C

2. 执行过程分步演示

初始化距离矩阵

动态规划过程（k为中间节点）

• k=0（A）：
  • 更新B→D：dist[B][D] = min(∞, 8+7) = ∞（无变化）
  • 更新C→B：dist[C][B] = min(∞, 5+3) = 8
• k=1（B）：
  • 更新A→C：dist[A][C] = min(∞, 3+2) = 5
  • 更新D→A：dist[D][A] = min(∞, 2+8) = 10
• k=2（C）：
  • 更新A→D：dist[A][D] = min(7, 5+1) = 6
  • 更新B→A：dist[B][A] = min(8, 2+5) = 7
• k=3（D）：
  • 更新A→B：dist[A][B] = min(3, 6+2) = 3（无变化）
  • 更新C→B：dist[C][B] = min(8, 1+2) = 3

最终距离矩阵

返回结果：

{'A': {'A':0, 'B':3, 'C':5, 'D':6},'B': {'A':7, 'B':0, 'C':2, 'D':3},'C': {'A':5, 'B':3, 'C':0, 'D':1},'D': {'A':9, 'B':2, 'C':4, 'D':0}
}

3. 关键点说明

1. 动态规划思想：通过中间节点 k 逐步优化所有顶点对 (i,j) 的路径。
2. 负权边处理：允许负权边，但图中不能有负权环（否则最短路径无意义）。
3. 时间复杂度：O(V³)，适合稠密图或顶点数较少的情况。
4. 空间优化：可原地修改矩阵，但代码中保留了清晰的中间状态。

4. 与 Dijkstra 的对比

5. 应用场景

• 网络路由表：计算所有路由器之间的最短路径。
• 交通规划：城市间最短路径的全局预计算。
• 游戏地图寻路：预先生成所有位置之间的移动成本。

6. 常见问题解答

Q1: 如何检测负权环？ 运行算法后，检查对角线元素 dist[i][i]：若存在 dist[i][i] < 0，则说明有负权环。

Q2: 如何重建具体路径？ 额外维护 next 矩阵记录路径：

next = [[None]*n for _ in range(n)]
# 初始化时：
if i != j and dist[i][j] != float('inf'):next[i][j] = j
# 更新时：
if dist[i][j] > dist[i][k] + dist[k][j]:dist[i][j] = dist[i][k] + dist[k][j]next[i][j] = next[i][k]  # 记录中间节点# 重建路径函数
def get_path(i, j):if next[i][j] is None:return []path = [i]while i != j:i = next[i][j]path.append(i)return path

Q3: 为什么用 inf 初始化？ inf 表示初始时顶点之间不可达，后续通过动态规划逐步更新为实际最短距离。

2. 最小生成树（MST）

Prim算法

import heapqdef prim(graph):if not graph:return []  # 空图直接返回mst = []               # 存储最小生成树的边visited = set()        # 记录已访问的顶点start = next(iter(graph))  # 随机选择一个起始顶点visited.add(start)# 初始化堆，存储起始顶点的所有边edges = [(weight, start, neighbor)for neighbor, weight in graph[start]]heapq.heapify(edges)  # 转换为最小堆while edges:weight, u, v = heapq.heappop(edges)  # 取出当前最小权重的边if v not in visited:visited.add(v)mst.append((u, v, weight))  # 加入最小生成树# 将新顶点的未访问邻居边加入堆for neighbor, weight in graph[v]:if neighbor not in visited:heapq.heappush(edges, (weight, v, neighbor))return mst

1. 核心步骤图示

假设有以下无向加权图（邻接表表示）：

graph = {'A': [('B', 2), ('D', 6)],'B': [('A', 2), ('C', 3), ('D', 8), ('E', 5)],'C': [('B', 3), ('E', 7)],'D': [('A', 6), ('B', 8), ('E', 9)],'E': [('B', 5), ('C', 7), ('D', 9)]
}

图示：

        A2↙   ↘6B     D3↙ \5 8↙ ↘9C   E7↙

2. 执行过程分步演示

从顶点 'A' 开始构建 MST：

最终 MST 边： [('A', 'B', 2), ('B', 'C', 3), ('B', 'E', 5), ('A', 'D', 6)] 总权重：2 + 3 + 5 + 6 = 16

3. 关键点说明

1. 贪心策略：每次选择当前连接已访问和未访问顶点的最小权重边。
2. 堆的作用：高效获取当前最小权重边（时间复杂度 O(log E)）。
3. 避免成环：仅处理未访问顶点的边（通过 visited 集合保证）。
4. 时间复杂度：O(E log E)，适合稠密图。

4. 与 Kruskal 算法的对比

5. 应用场景

• 网络设计：构建成本最低的通信网络。
• 电路板布线：最小化导线总长度。
• 管道系统：优化水/电管道的连接路径。

6. 常见问题解答

Q1: 如何处理非连通图？ Prim 算法只能得到连通分量的 MST。若图不连通，需对每个连通分量分别运行 Prim。

Q2: 如何验证结果的正确性？ 检查以下条件：

1. 边数 = 顶点数 - 1。
2. 总权重与 Kruskal 算法结果一致。
3. 无环且连接所有顶点。

Q3: 为什么不用优先队列而用堆？ Python 的 heapq 模块实现的是最小堆，本质上就是优先队列的高效实现。

Kruskal算法

def kruskal(graph):parent = {}  # 并查集数据结构# 查找根节点（路径压缩优化）def find(u):while parent[u] != u:parent[u] = parent[parent[u]]  # 路径压缩u = parent[u]return u# 合并两个集合def union(u, v):u_root = find(u)v_root = find(v)if u_root == v_root:return False  # 已在同一集合，无需合并parent[v_root] = u_rootreturn True# 1. 初始化所有边并按权重排序edges = []for u in graph:parent[u] = u  # 每个节点初始时自成一集合for v, weight in graph[u]:edges.append((weight, u, v))edges.sort()  # 按权重升序排序# 2. 遍历所有边，构建MSTmst = []for weight, u, v in edges:if union(u, v):  # 如果边不会形成环mst.append((u, v, weight))return mst

1. 核心步骤图示

假设有以下无向加权图（邻接表表示）：

graph = {'A': [('B', 2), ('D', 6)],'B': [('A', 2), ('C', 3), ('D', 8), ('E', 5)],'C': [('B', 3), ('E', 7)],'D': [('A', 6), ('B', 8), ('E', 9)],'E': [('B', 5), ('C', 7), ('D', 9)]
}

图示：

2. 执行过程分步演示

步骤1：边排序

所有边按权重升序排序：

(2,A,B), (3,B,C), (5,B,E), (6,A,D), (7,C,E), (8,B,D), (9,D,E)

步骤2：构建MST

最终 MST 边： [('A', 'B', 2), ('B', 'C', 3), ('B', 'E', 5), ('A', 'D', 6)] 总权重：2 + 3 + 5 + 6 = 16

3. 关键点说明

1. 并查集优化：
   • find 函数使用路径压缩，降低后续查找时间复杂度。
   • union 函数通过比较根节点避免环的形成。
2. 贪心策略：按权重升序选择边，确保每次加入的边是当前最小的有效边。
3. 时间复杂度：
   • 排序：O(E log E)
   • 并查集操作：O(α(V))（近似常数）
   • 总复杂度：O(E log E)（适合稀疏图）

4. 与 Prim 算法的对比

5. 应用场景

• 电网设计：用最小成本连接所有城市。
• 道路规划：建设总长度最短的公路网。
• 聚类分析：基于距离合并相似数据点。

6. 常见问题解答

Q1: 如何验证结果的正确性？ 检查：

1. 边数 = 顶点数 - 1
2. 总权重与 Prim 算法结果一致
3. 通过并查集确认无环

Q2: 如何处理非连通图？ 算法会返回最小生成森林（各连通分量的 MST），可通过检查 parent 中根节点的数量判断连通性。

Q3: 为什么边排序用 sort() 而不是堆？

• 排序后只需一次遍历（O(E)），而堆需要多次弹出（O(E log E)）。
• 实际时间复杂度相同，但排序代码更简洁。

3. 拓扑排序（DAG）

from collections import dequedef topological_sort(graph):# 1. 计算所有顶点的入度in_degree = {u: 0 for u in graph}for u in graph:for v, _ in graph[u]:  # 忽略权重in_degree[v] += 1# 2. 初始化队列（入度为0的顶点）queue = deque([u for u in in_degree if in_degree[u] == 0])topo_order = []# 3. 不断移除入度为0的顶点while queue:u = queue.popleft()topo_order.append(u)for v, _ in graph[u]:in_degree[v] -= 1  # 删除边u→vif in_degree[v] == 0:queue.append(v)# 4. 检查是否存在环if len(topo_order) == len(graph):return topo_order  # 有效拓扑序else:return []  # 存在环，无法拓扑排序

1. 核心步骤图示

假设有以下有向无环图（DAG）（邻接表表示）：

graph = {'A': [('B', 1), ('C', 1)],  # A → B, A → C'B': [('D', 1)],             # B → D'C': [('D', 1), ('E', 1)],   # C → D, C → E'D': [('F', 1)],             # D → F'E': [('F', 1)],             # E → F'F': []                      # F 无出边
}

图示：

      A/   \B     C\  /  \D     E\   /F

2. 执行过程分步演示

步骤1：计算入度

步骤2：初始化队列

queue = deque(['A']) （只有A的入度为0）

步骤3：处理队列

最终拓扑序：['A', 'B', 'C', 'D', 'E', 'F'] （其他可能的拓扑序：['A', 'C', 'E', 'B', 'D', 'F']）

3. 关键点说明

1. 入度（In-degree）：指向顶点的边数量，用于确定可处理的顶点。
2. 队列选择：优先处理入度为0的顶点（保证无前驱依赖）。
3. 环检测：若结果列表长度 ≠ 顶点数，说明存在环。
4. 时间复杂度：O(V + E)，适合大规模DAG。

4. 应用场景

• 任务调度：编译器的依赖管理（如Makefile）。
• 课程安排：选修课的先后顺序规划。
• 工作流引擎：步骤的依赖关系处理。

5. 常见问题解答

Q1: 如何处理非DAG图？ 算法会返回空列表（如检测到环），例如：

graph = {'A': [('B',1)], 'B': [('A',1)]}  # A↔B
print(topological_sort(graph))  # []（存在环）

Q2: 如何获取所有可能的拓扑序？ 需用回溯法枚举所有可能的顺序，但时间复杂度较高（O(V!)）。

Q3: 为什么用队列而不用栈？ 队列保证BFS顺序（广度优先），栈实现DFS顺序（深度优先）。两者均可得到有效拓扑序，但顺序不同。

6. 扩展：动态图中维护拓扑序

对于频繁增删边的图，可使用增量式拓扑排序算法（如Kahn算法的动态版本）。

图的高级应用

1. 连通分量检测

def connected_components(graph):visited = set()                     # 记录已访问顶点components = []                     # 存储所有连通分量for vertex in graph:                # 遍历每个顶点if vertex not in visited:# 初始化DFS栈stack = [vertex]visited.add(vertex)component = []              # 当前连通分量while stack:node = stack.pop()      # 弹出栈顶顶点component.append(node)# 遍历邻居for neighbor, _ in graph[node]:  # 忽略权重if neighbor not in visited:visited.add(neighbor)stack.append(neighbor)components.append(component)return components

1. 核心步骤图示

假设有以下无向图（邻接表表示，权重忽略）：

graph = {'A': [('B', 1), ('C', 1)],'B': [('A', 1), ('C', 1)],'C': [('A', 1), ('B', 1)],'D': [('E', 1)],'E': [('D', 1)],'F': []
}

图示：

      A/   \B     C    D — E   F（孤立）

2. 执行过程分步演示

步骤1：初始化

• visited = {}
• components = []

步骤2：处理顶点A

• 发现A未访问，启动DFS：
  • 栈初始化：stack = ['A']
  • 访问A的邻居B、C：
    • 将B、C加入栈和visited
  • 弹出C，访问其邻居A、B（A已访问）：
    • 无新节点加入
  • 弹出B，访问其邻居A、C（均已访问）
• 当前连通分量：['A', 'C', 'B']

步骤3：处理顶点D

• 发现D未访问，启动DFS：
  • 栈初始化：stack = ['D']
  • 访问D的邻居E：
    • 将E加入栈和visited
  • 弹出E，访问其邻居D（已访问）
• 当前连通分量：['D', 'E']

步骤4：处理顶点F

• 发现F未访问且无邻居：
• 当前连通分量：['F']

最终结果：

[ ['A', 'C', 'B'], ['D', 'E'], ['F'] ]

3. 关键点说明

1. DFS/BFS选择：代码使用DFS（栈实现），也可改用BFS（队列实现）。
2. 无向图处理：算法隐式处理无向边（如A-B和B-A视为同一条边）。
3. 时间复杂度：O(V + E)，每个顶点和边仅处理一次。
4. 权重忽略：for neighbor, _ in graph[node] 中的 _ 表示忽略权重。

4. 与强连通分量（SCC）的区别

5. 应用场景

• 社交网络分析：识别用户群体（如微信群组）。
• 电路设计：检测电路板的连通区域。
• 图像处理：分割图像中的连通像素区域。

6. 常见问题解答

Q1: 如何判断图是否连通？ 检查components的长度是否为1：

def is_connected(graph):return len(connected_components(graph)) == 1

Q2: 如何处理有向图的连通性？ 有向图的连通性分为：

• 弱连通：忽略方向后无向图连通（可用本算法）。
• 强连通：需用Kosaraju/Tarjan算法。

Q3: 如何优化大规模图的性能？

• 使用迭代DFS/BFS避免递归栈溢出。
• 并行化处理不同连通分量。

2. 强连通分量（Kosaraju算法）

def kosaraju(graph):# 第一次DFS：记录顶点处理完成顺序visited = set()order = []def dfs(u):stack = [(u, False)]  # (顶点, 是否已处理)while stack:node, processed = stack.pop()if processed:order.append(node)  # 后序记录continueif node in visited:continuevisited.add(node)stack.append((node, True))  # 标记为已处理for v, _ in graph.get(node, []):  # 遍历邻居if v not in visited:stack.append((v, False))# 对每个未访问顶点执行DFSfor u in graph:if u not in visited:dfs(u)# 构建反向图reversed_graph = {}for u in graph:for v, w in graph[u]:reversed_graph.setdefault(v, []).append((u, w))# 第二次DFS：按逆序处理反向图visited = set()scc = []  # 存储强连通分量for u in reversed(order):  # 按第一次DFS的逆序处理if u not in visited:stack = [u]visited.add(u)component = []while stack:node = stack.pop()component.append(node)for v, _ in reversed_graph.get(node, []):if v not in visited:visited.add(v)stack.append(v)scc.append(component)return scc

1. 核心步骤图示

假设有以下有向图：

graph = {'A': [('B', 1)],'B': [('C', 1), ('E', 1)],'C': [('D', 1)],'D': [('A', 1), ('C', 1)],'E': [('F', 1)],'F': [('G', 1)],'G': [('E', 1)],'H': [('I', 1)],'I': []
}

图示：

A → B → C ←→ D↘E ←→ F ←→ G
H → I

2. 执行过程分步演示

步骤1：第一次DFS（记录处理顺序）

• DFS顺序（后序遍历）：
  1. 从A出发：访问A→B→C→D（D完成后回溯）
     • 记录顺序：D, C, B, A
  2. 从E出发：访问E→F→G（G完成后回溯）
     • 记录顺序：G, F, E
  3. 从H出发：访问H→I
     • 记录顺序：I, H
• 最终order：['D', 'C', 'B', 'A', 'G', 'F', 'E', 'I', 'H']

步骤2：构建反向图

A ← B ← C ←→ D↖E ←→ F ←→ G
H ← I

步骤3：第二次DFS（按order逆序处理反向图）

最终SCC结果：

[['A', 'D', 'C', 'B'],  # A-B-C-D强连通['E', 'G', 'F'],       # E-F-G强连通['H'],                 # 独立顶点['I']                  # 独立顶点
]

3. 关键点说明

1. 两次DFS的必要性：
   • 第一次DFS确定顶点的处理顺序（保证反向图中SCC的拓扑序）。
   • 第二次DFS在反向图中识别SCC。
2. 反向图的作用：将原图的边反向，使得SCC内部的顶点仍能互相访问，而不同SCC之间隔离。
3. 时间复杂度：O(V + E)，每个顶点和边被处理两次。

4. 与Tarjan算法的对比

5. 应用场景

• 编译器优化：识别代码中的循环依赖。
• 社交网络：发现紧密互动的用户群体。
• 网页链接分析：确定网页社区的强关联子集。

6. 常见问题解答

Q1: 为什么第一次DFS要用后序遍历？ 后序遍历确保在反向图中，一个SCC的顶点会在其依赖的其他SCC之前被处理。

Q2: 如何处理非强连通的有向图？ 算法会自动将图分解为多个SCC，非强连通的部分会作为独立SCC返回。

Q3: 如何验证结果的正确性？ 检查：

1. 每个SCC内部任意两顶点双向可达。
2. 不同SCC之间无双向路径。

3. 最大流问题（Ford-Fulkerson算法）

from collections import dequedef ford_fulkerson(graph, source, sink):# 1. 初始化残量图（包含反向边）residual = {u: {} for u in graph}for u in graph:for v, cap in graph[u]:residual[u][v] = cap  # 正向边初始容量residual[v][u] = 0    # 反向边初始为0parent = {}      # 记录增广路径max_flow = 0     # 最大流结果# 2. BFS寻找增广路径def bfs():visited = set()queue = deque([source])visited.add(source)while queue:u = queue.popleft()for v in residual[u]:if v not in visited and residual[u][v] > 0:visited.add(v)parent[v] = uif v == sink:return True  # 找到增广路径queue.append(v)return False  # 无增广路径# 3. 不断寻找增广路径并更新残量图while bfs():# 计算路径最小残量path_flow = float('inf')v = sinkwhile v != source:u = parent[v]path_flow = min(path_flow, residual[u][v])v = u# 更新残量图（正向边减，反向边加）v = sinkwhile v != source:u = parent[v]residual[u][v] -= path_flowresidual[v][u] += path_flowv = umax_flow += path_flowreturn max_flow

1. 核心步骤图示

假设有以下流网络（邻接表表示）：

graph = {'s': [('a', 3), ('b', 2)],  # s为源点'a': [('c', 3), ('d', 2)],'b': [('d', 3)],'c': [('t', 2)],            # t为汇点'd': [('t', 3)],'t': []
}

初始残量图：

       3a → c↗     ↘
s         t↘     ↗b → d3

2. 执行过程分步演示

第一次迭代：

• BFS路径：s → a → c → t
  • 路径最小残量：min(3, 3, 2) = 2
  • 更新残量：
    • s-a: 3→1, a-c: 3→1, c-t: 2→0
    • 反向边：a-s: 0→2, c-a: 0→2, t-c: 0→2
• 当前流量：0 → 2

第二次迭代：

• BFS路径：s → a → d → t
  • 路径最小残量：min(1, 2, 3) = 1
  • 更新残量：
    • s-a: 1→0, a-d: 2→1, d-t: 3→2
    • 反向边：a-s: 2→3, d-a: 0→1, t-d: 0→1
• 当前流量：2 → 3

第三次迭代：

• BFS路径：s → b → d → t
  • 路径最小残量：min(2, 3, 2) = 2
  • 更新残量：
    • s-b: 2→0, b-d: 3→1, d-t: 2→0
    • 反向边：b-s: 0→2, d-b: 0→2, t-d: 1→3
• 当前流量：3 → 5

终止条件：

• 无法再找到从 s 到 t 的增广路径
• 最终最大流：5

3. 关键点说明

1. 残量图（Residual Graph）：
   • 正向边：剩余容量 = 原始容量 - 已用流量
   • 反向边：允许“撤销”流量（实现贪心算法的回退）
2. 增广路径：残量图中从源点到汇点的路径，其最小残量决定可增加的流量。
3. 时间复杂度：O(E * max_flow)，最坏情况下效率低（如边权为无理数时可能不终止）。

4. 与Edmonds-Karp算法的关系

Ford-Fulkerson 是框架，而 Edmonds-Karp 是其特例（规定用BFS找最短增广路径，时间复杂度优化为O(V E²)）。

5. 应用场景

• 交通网络：计算道路的最大通行能力。
• 水管系统：确定输水管道的最大流量。
• 数据流分析：网络数据传输的带宽优化。

6. 常见问题解答

Q1: 为什么需要反向边？ 反向边允许算法“撤销”之前的流量分配，确保能找到全局最优解（如允许流量从a→b后又从b→a回流）。

Q2: 如何记录具体的流量分配方案？ 在更新残量图时，记录原始边的流量变化：

flow = {u: {v: 0 for v in graph} for u in graph}
# 在更新残量图时同步：
flow[u][v] += path_flow

Q3: 如何处理多源点/多汇点问题？ 添加超级源点和超级汇点：

• 超级源点连接到所有源点，容量为无穷大。
• 所有汇点连接到超级汇点，容量为无穷大。

图算法复杂度对比

图数据库与处理框架

1. 图数据库

• Neo4j：最流行的原生图数据库
• JanusGraph：可扩展的分布式图数据库
• Amazon Neptune：全托管的图数据库服务

2. 图处理框架

• Apache Giraph：基于Hadoop的图处理
• GraphX：Spark的图计算API
• NetworkX：Python图分析库

常见面试问题

1. 克隆图（深拷贝）
2. 课程表安排（拓扑排序）
3. 岛屿数量（连通分量）
4. 单词接龙（最短路径）
5. 朋友圈（并查集）
6. 网络延迟时间（Dijkstra）
7. 最小高度树（图中心）
8. 重新安排行程（欧拉路径）
9. 除法求值（加权图）
10. 水管网络（最大流）

学习建议

1. 可视化工具：使用Graphviz或在线工具观察图结构
2. 分步调试：手动模拟算法执行过程
3. 比较学习：对比不同算法的适用场景
4. 实际问题：将社交网络等现实问题抽象为图
5. 竞赛练习：LeetCode/Codeforces图论题目

总结：图的思维模式

图论不仅是一组算法，更是一种强大的建模工具：

• 抽象能力：将复杂系统简化为节点和边
• 算法思维：掌握经典范型（贪心、动态规划等）
• 跨领域应用：从社交网络到生物信息学

掌握图的关键在于：

1. 理解不同表示方法的优缺点
2. 熟练核心算法及其变体
3. 培养将实际问题转化为图问题的能力
4. 了解现代图处理系统和框架

记住：图是描述关系的通用语言，掌握这种语言将为你打开解决复杂问题的新视角。无论是系统设计还是算法优化，图结构都将继续在计算机科学的未来扮演核心角色。