Chapter 5 Graph

AOV（Activity On Vertex）网络是图论中的一种数据结构，用于表示活动之间的依赖关系。以下是其核心要点：

1. 基本定义

• 顶点表示活动：每个顶点代表一个独立的任务或活动
• 有向边表示依赖：边A→B表示活动A必须在活动B之前完成（B依赖A）

2. 关键特性

• 必须是有向无环图（DAG）
• 不允许出现循环依赖（如A→B→C→A）
• 边本身不携带权重（仅表示依赖关系）

3. 拓扑排序应用

通过拓扑排序可以确定合法的执行顺序：

def topological_sort(graph):
    in_degree = {u:0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([u for u in in_degree if in_degree[u] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    return result if len(result) == len(graph) else "存在环"

4. 典型应用场景

• 课程选修顺序（先修课要求）
• 软件构建的编译顺序
• 产品生产流程规划
• 项目管理中的任务调度

5. 与AOE网络的对比

6. 实践注意事项

• 必须进行环检测（时间复杂度O(V+E)）
• 可能存在多个有效拓扑排序结果
• 实际应用中常结合关键路径分析进行优化

拓扑序列（Topological Ordering）是有向无环图（DAG）中顶点的一种线性排列，满足图中所有有向边从前驱顶点指向后继顶点的顺序关系。以下是其核心要点：

1. 核心定义

• 依赖顺序的体现：若存在边 u→v，则在拓扑序列中顶点 u 必须出现在顶点 v 之前。
• DAG的必然属性：只有无环的有向图才能存在拓扑序列（若存在环，则无法找到合法排序）。

2. 关键特性

3. 生成算法

Kahn算法（基于入度）

```python from collections import deque

def topological_sort(graph): in_degree = {u: 0 for u in graph} # 计算初始入度

• Pick : 选择顶点
• Relax : 更新路径/权重

1. Pick 操作

定义

• Pick（选择操作）：从候选集合中选择一个顶点，用于后续处理。具体选择策略取决于算法目标：
• 最短路径算法（如 Dijkstra）：选择当前距离起点最近的未处理顶点。
• 最小生成树算法（如 Prim）：选择当前距离生成树最近的顶点。

作用

• 确定算法的处理顺序，确保每一步都朝着最优解推进。
• 避免重复处理已确定最短路径或已加入生成树的顶点。

示例

• Dijkstra 算法：

  def dijkstra(graph, start):
      dist = {v: ∞ for v in graph.vertices}  # 初始化距离为无穷大
      dist[start] = 0
      visited = set()
      priority_queue = PriorityQueue()       # 优先队列按距离排序
      priority_queue.add(start, 0)
  
      while not priority_queue.empty():
          u = priority_queue.extract_min()  # Pick 操作：选择距离最小的顶点
          visited.add(u)
          for v in u.neighbors:
              relax(u, v, graph.edge(u, v))  # Relax 操作
  

2. Relax 操作

定义

• Relax（松弛操作）：检查是否可以通过某个顶点 u 到达顶点 v 的路径更短（或更优），如果是，则更新 v 的最短距离或权重。
• 数学描述（最短路径算法）：

  if dist[v] > dist[u] + weight(u, v):
      dist[v] = dist[u] + weight(u, v)
      prev[v] = u
  

作用

• 动态更新顶点的最短路径估计值。
• 逐步逼近全局最优解。

示例

• Dijkstra 算法中的 Relax：

  def relax(u, v, weight):
      if dist[v] > dist[u] + weight:
          dist[v] = dist[u] + weight
          prev[v] = u
          priority_queue.decrease_key(v, dist[v])  # 更新优先级队列
  

3. Pick 和 Relax 的协同工作

以 Dijkstra 算法 为例，两者的协作流程如下： 1. 初始化：起点距离为 0，其他顶点距离为 ∞。 2. Pick：从优先队列中选择距离最小的顶点 u。 3. Relax：遍历 u 的所有邻接顶点 v，尝试通过 u 更新 v 的距离。 4. 重复：直到所有顶点被处理。

可视化流程

初始状态：
顶点 A(0), B(∞), C(∞), D(∞)

Pick A → Relax A→B 和 A→C：
顶点 A(0), B(2), C(5), D(∞)

Pick B → Relax B→C 和 B→D：
顶点 A(0), B(2), C(3), D(7)

Pick C → Relax C→D：
顶点 A(0), B(2), C(3), D(5)

Pick D → 结束。

4. 不同算法中的 Pick 和 Relax

Dijkstra 算法

• Pick：使用优先队列选择距离起点最近的未处理顶点。
• Relax：更新邻接顶点的最短距离。
• 适用场景：无负权边的图。

Bellman-Ford 算法

• Pick：无显式选择操作，直接遍历所有边。
• Relax：对所有边进行松弛，重复 V-1 次。
• 适用场景：含负权边的图（可检测负权环）。

Prim 算法 x
- Pick：选择距离生成树最近的顶点。 - Relax：更新未加入生成树顶点的最小权重。 - 目标：构建最小生成树。

5. 关键区别 | 算法 | Pick 操作 | Relax 操作 | 时间复杂度 | |----------------|-----------------------------|-------------------------------------|-------------------| | Dijkstra | 优先队列选择最小距离顶点 | 更新邻接顶点的最短路径 | O((V+E) log V) | | Bellman-Ford| 无显式选择，遍历所有边 | 对所有边进行松弛操作，重复 V-1 次 | O(V·E) | | Prim | 优先队列选择最小权重边的顶点 | 更新未加入生成树顶点的最小权重 | O((V+E) log V) |

6. 代码示例（Dijkstra 算法）

import heapq

def dijkstra(graph, start):
    dist = {v: float('inf') for v in graph}
    dist[start] = 0
    heap = [(0, start)]
    visited = set()

    while heap:
        current_dist, u = heapq.heappop(heap)  # Pick 操作
        if u in visited:
            continue
        visited.add(u)

        for v, weight in graph[u].items():
            if dist[v] > dist[u] + weight:    # Relax 条件
                dist[v] = dist[u] + weight    # Relax 操作
                heapq.heappush(heap, (dist[v], v))

    return dist