Skip to content

XiaoMaColtAI/math-modeling-skill

math-modeling

Verified

当用户要求数学建模、建模竞赛、建模分析、代码求解、结果可视化或生成数学建模论文时使用。支持完整三阶段流程、单独执行任一角色,以及在关键节点使用独立 Subagent 进行阶段内质检;默认只启用质检 Subagent,用户可明确选择额外协作。

assets/04-图论与网络分析算法说明.md

View on GitHub
# 图论与网络分析算法说明文档

## 概述

图论与网络分析是数学建模中的重要算法类型,用于处理离散结构和网络优化问题。图论问题广泛存在于交通运输、通信网络、物流配送、社交网络等领域。

---

## 1. 最短路径问题 (Shortest Path Problem)

### 算法介绍

最短路径问题是指在给定网络图中,寻找两个顶点之间总权重最小的路径。

#### 1.1 Dijkstra算法

适用于**非负权图**,是求解单源最短路径的经典算法。

**核心思想**:贪心策略,每次选择距离源点最近的未访问顶点。

**算法步骤**:
1. 初始化:源点距离为0,其他顶点距离为∞
2. 选择未访问顶点中距离最小的顶点$u$
3. 松弛$u$的所有邻接边:若$dist[v] > dist[u] + w(u,v)$,则更新$dist[v]$
4. 重复2-3直到所有顶点都被访问

**时间复杂度**:$O((V+E)\log V)$(使用优先队列)

**距离更新公式**:
$$
dist[v] = \min\{dist[v], dist[u] + w(u, v)\}
$$

#### 1.2 Bellman-Ford算法

适用于**含负权边**的图,可检测负权回路。

**松弛操作**:
$$
dist[v] = \min\{dist[v], dist[u] + w(u, v)\}
$$

对所有边进行$|V|-1$轮松弛。

**时间复杂度**:$O(VE)$

#### 1.3 Floyd-Warshall算法

适用于**全源最短路径**,可处理负权边(不含负权回路)。

**状态转移方程**:
$$
dp[i][j][k] = \min\{dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1]\}
$$

简写为:
$$
dist[i][j] = \min\{dist[i][j], dist[i][k] + dist[k][j]\}
$$

**时间复杂度**:$O(V^3)$

### 适用范围

| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 路径规划 | 导航系统、物流配送 | 最小费用路径 |
| 网络路由 | 数据包路由 | 最快路径 |
| 交通规划 | 城市交通路径 | 最短时间/距离 |
| 供应链优化 | 供应商到工厂 | 最小成本 |
| 通信网络 | 信号传输路径 | 最小延迟 |

### 可视化图表类型

- **网络图**:顶点与边的可视化
- **路径标注图**:最短路径高亮显示
- **距离矩阵热力图**:顶点间距离
- **迭代过程图**:算法迭代过程
- **三维路径图**:三维空间中的路径

### 关键文献

| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| A note on two problems in connexion with graphs | Dijkstra | 1959 | Numerische Mathematik |
| Algorithm for the shortest path problem | Bellman | 1958 | Quarterly of Applied Mathematics |
| A Algorithm for Path Problems and Matrix Multiplication | Floyd | 1962 | Communications of the ACM |

### 代码实现要点

```python
import heapq
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
from matplotlib.patches import FancyArrowPatch
import warnings
warnings.filterwarnings('ignore')

# 设置中文字体 - 多字体备选防止渲染问题
plt.rcParams['font.sans-serif'] = ['SimHei', 'DejaVu Sans', 'Arial Unicode MS', 'Microsoft YaHei', 'Arial']
plt.rcParams['axes.unicode_minus'] = False

class ShortestPathAlgorithms:
    """
    最短路径算法集合
    """
    
    @staticmethod
    def dijkstra(graph, start, end=None):
        """
        Dijkstra最短路径算法
        :param graph: 图的邻接表 {顶点: {邻居: 权重}}
        :param start: 起点
        :param end: 终点,若为None则计算到所有点的最短路径
        :return: 最短距离字典, 前驱节点字典
        """
        distances = {vertex: float('infinity') for vertex in graph}
        distances[start] = 0
        previous = {vertex: None for vertex in graph}
        
        pq = [(0, start)]
        visited = set()
        
        while pq:
            current_distance, current = heapq.heappop(pq)
            
            if current in visited:
                continue
            visited.add(current)
            
            if end and current == end:
                break
            
            for neighbor, weight in graph[current].items():
                if neighbor in visited:
                    continue
                distance = current_distance + weight
                if distance < distances[neighbor]:
                    distances[neighbor] = distance
                    previous[neighbor] = current
                    heapq.heappush(pq, (distance, neighbor))
        
        return distances, previous
    
    @staticmethod
    def reconstruct_path(previous, start, end):
        """根据前驱节点重建路径"""
        path = []
        current = end
        while current is not None:
            path.append(current)
            current = previous[current]
        path.reverse()
        return path if path[0] == start else []
    
    @staticmethod
    def bellman_ford(graph, start):
        """
        Bellman-Ford算法(可处理负权边)
        :param graph: 图的邻接表
        :param start: 起点
        :return: 最短距离字典, 前驱节点字典, 是否存在负权回路
        """
        distances = {vertex: float('infinity') for vertex in graph}
        distances[start] = 0
        previous = {vertex: None for vertex in graph}
        
        # 松弛操作 |V|-1 次
        for _ in range(len(graph) - 1):
            updated = False
            for u in graph:
                for v, weight in graph[u].items():
                    if distances[u] + weight < distances[v]:
                        distances[v] = distances[u] + weight
                        previous[v] = u
                        updated = True
            if not updated:
                break
        
        # 检测负权回路
        has_negative_cycle = False
        for u in graph:
            for v, weight in graph[u].items():
                if distances[u] + weight < distances[v]:
                    has_negative_cycle = True
                    break
        
        return distances, previous, has_negative_cycle
    
    @staticmethod
    def floyd_warshall(adjacency_matrix):
        """
        Floyd-Warshall全源最短路径算法
        :param adjacency_matrix: 邻接矩阵(inf表示不可达)
        :return: 距离矩阵, 前驱矩阵
        """
        n = len(adjacency_matrix)
        dist = np.array(adjacency_matrix, dtype=float)
        next_node = np.full((n, n), None, dtype=object)
        
        # 初始化
        for i in range(n):
            for j in range(n):
                if dist[i][j] != float('infinity') and i != j:
                    next_node[i][j] = j
                if i == j:
                    dist[i][j] = 0
        
        # 动态规划
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if dist[i][k] + dist[k][j] < dist[i][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        next_node[i][j] = next_node[i][k]
        
        return dist, next_node
    
    @staticmethod
    def reconstruct_floyd_path(next_node, start, end):
        """重建Floyd-Warshall路径"""
        if next_node[start][end] is None:
            return []
        path = [start]
        while start != end:
            start = next_node[start][end]
            path.append(start)
        return path

def visualize_shortest_path(graph, start, end, shortest_path, distances):
    """可视化最短路径结果"""
    fig, axes = plt.subplots(1, 2, figsize=(16, 7))
    
    # 创建NetworkX图
    G = nx.DiGraph()
    for u in graph:
        for v, weight in graph[u].items():
            G.add_edge(u, v, weight=weight)
    
    # 布局
    pos = nx.spring_layout(G, k=2, iterations=50, seed=42)
    
    # 图1:网络图和最短路径
    ax1 = axes[0]
    
    # 绘制所有边
    edge_labels = {(u, v): f'{d["weight"]}' for u, v, d in G.edges(data=True)}
    nx.draw_networkx_edges(G, pos, ax=ax1, edge_color='gray', alpha=0.5, 
                           arrows=True, arrowsize=20, width=1.5)
    
    # 高亮最短路径
    if len(shortest_path) > 1:
        path_edges = [(shortest_path[i], shortest_path[i+1]) 
                     for i in range(len(shortest_path)-1)]
        nx.draw_networkx_edges(G, pos, ax=ax1, edgelist=path_edges, 
                              edge_color='red', width=3, arrows=True, arrowsize=25)
    
    # 绘制节点
    node_colors = ['lightgreen' if node == start else 'lightcoral' if node == end 
                   else 'lightblue' for node in G.nodes()]
    nx.draw_networkx_nodes(G, pos, ax=ax1, node_color=node_colors, 
                          node_size=800, edgecolors='black', linewidths=2)
    nx.draw_networkx_labels(G, pos, ax=ax1, font_size=12, font_weight='bold')
    
    # 边权重标签
    nx.draw_networkx_edge_labels(G, pos, edge_labels, ax=ax1, font_size=9)
    
    ax1.set_title(f'最短路径: {" -> ".join(shortest_path)}\n总距离: {distances[end]}', fontsize=14)
    ax1.axis('off')
    
    # 图2:距离分布
    ax2 = axes[1]
    
    # 从起点到各点的距离
    nodes = list(distances.keys())
    dists = [distances[n] if distances[n] != float('infinity') else 0 for n in nodes]
    
    colors = ['green' if n == start else 'red' if n == end else 'skyblue' for n in nodes]
    bars = ax2.bar(nodes, dists, color=colors, edgecolor='black', alpha=0.7)
    
    # 添加数值标签
    for bar, dist in zip(bars, dists):
        if dist > 0:
            height = bar.get_height()
            ax2.text(bar.get_x() + bar.get_width()/2., height,
                    f'{dist:.0f}', ha='center', va='bottom', fontsize=10)
    
    ax2.set_xlabel('节点', fontsize=12)
    ax2.set_ylabel('最短距离', fontsize=12)
    ax2.set_title(f'从 {start} 到各节点的最短距离', fontsize=14)
    plt.tight_layout()
    plt.savefig('shortest_path_results.png', dpi=150, bbox_inches='tight')
    plt.show()
    
    print("\n图表已保存为 'shortest_path_results.png'")

# 运行示例
if __name__ == "__main__":
    print("=" * 60)
    print("最短路径算法示例")
    print("=" * 60)
    
    # 示例图(城市交通网络)
    graph = {
        'A': {'B': 4, 'C': 2},
        'B': {'C': 1, 'D': 5, 'E': 3},
        'C': {'D': 8, 'E': 10},
        'D': {'E': 2, 'F': 6},
        'E': {'F': 3},
        'F': {}
    }
    
    start_node = 'A'
    end_node = 'F'
    
    print(f"\n图结构:")
    for node, neighbors in graph.items():
        print(f"  {node}: {neighbors}")
    
    print(f"\n起点: {start_node}")
    print(f"终点: {end_node}")
    
    # Dijkstra算法
    print("\n" + "=" * 60)
    print("Dijkstra算法结果")
    print("=" * 60)
    
    spa = ShortestPathAlgorithms()
    distances, previous = spa.dijkstra(graph, start_node, end_node)
    shortest_path = spa.reconstruct_path(previous, start_node, end_node)
    
    print(f"最短路径: {' -> '.join(shortest_path)}")
    print(f"最短距离: {distances[end_node]}")
    
    print("\n从起点到各节点的距离:")
    for node, dist in sorted(distances.items()):
        if dist != float('infinity'):
            print(f"  {start_node} -> {node}: {dist}")
    
    # Floyd-Warshall算法
    print("\n" + "=" * 60)
    print("Floyd-Warshall算法结果")
    print("=" * 60)
    
    # 构建邻接矩阵
    nodes = list(graph.keys())
    n = len(nodes)
    node_index = {node: i for i, node in enumerate(nodes)}
    
    inf = float('infinity')
    adj_matrix = [[inf] * n for _ in range(n)]
    for i in range(n):
        adj_matrix[i][i] = 0
    
    for u in graph:
        for v, weight in graph[u].items():
            adj_matrix[node_index[u]][node_index[v]] = weight
    
    dist_matrix, next_matrix = spa.floyd_warshall(adj_matrix)
    
    print("全源最短距离矩阵:")
    print("    ", "  ".join([f"{node:4s}" for node in nodes]))
    for i, node in enumerate(nodes):
        row = [f"{dist_matrix[i][j]:4.0f}" if dist_matrix[i][j] != inf else "  inf" 
               for j in range(n)]
        print(f"{node}: ", "  ".join(row))
    
    # 可视化
    visualize_shortest_path(graph, start_node, end_node, shortest_path, distances)
```

---

## 2. 最小生成树问题 (Minimum Spanning Tree, MST)

### 算法介绍

最小生成树是指在一个连通的无向图中,找到一棵包含所有顶点且总权重最小的树。

#### 2.1 Prim算法

从一个顶点开始,逐步添加权重最小的边,直到包含所有顶点。

**算法步骤**:
1. 选择任意顶点作为起始点
2. 在已访问顶点和未访问顶点之间找权重最小的边
3. 将该边和对应顶点加入树
4. 重复2-3直到所有顶点都被访问

**时间复杂度**:$O(E \log V)$(使用优先队列)

#### 2.2 Kruskal算法

按边的权重从小到大选择,不形成回路则加入,直到有$V-1$条边。

**算法步骤**:
1. 将所有边按权重排序
2. 从小到大选择边
3. 若边连接两个不同连通分量,则加入
4. 重复2-3直到有$V-1$条边

使用**并查集**检测回路。

**时间复杂度**:$O(E \log E)$

### 适用范围

| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 网络设计 | 通信网络、电力网络 | 连接成本最小 |
| 交通规划 | 道路建设规划 | 建设费用最小 |
| 管网布局 | 水管、气管布局 | 铺设成本最小 |
| 电路设计 | PCB布线 | 线路最短 |
| 聚类分析 | 层次聚类 | 相似度最大 |

### 可视化图表类型

- **生成树图**:MST边的高亮显示
- **构造过程图**:算法逐步构造过程
- **权重分布图**:边权重的分布
- **树状结构图**:MST的树形结构
- **对比图**:不同算法结果对比

### 关键文献

| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Shortest connection networks and some generalizations | Prim | 1957 | Bell System Technical Journal |
| On the shortest spanning subtree of a graph and the traveling salesman problem | Kruskal | 1956 | Proceedings of the AMS |

### 代码实现要点

```python
import heapq

def prim(graph):
    """
    Prim最小生成树算法
    :param graph: 图的邻接表 {顶点: {邻居: 权重}}
    :return: MST边列表, 总权重
    """
    if not graph:
        return [], 0

    start = next(iter(graph.keys()))
    visited = set([start])
    edges = []

    # 初始化优先队列
    for neighbor, weight in graph[start].items():
        heapq.heappush(edges, (weight, start, neighbor))

    mst_edges = []
    total_weight = 0

    while edges and len(visited) < len(graph):
        weight, u, v = heapq.heappop(edges)

        if v in visited:
            continue

        visited.add(v)
        mst_edges.append((u, v, weight))
        total_weight += weight

        for neighbor, w in graph[v].items():
            if neighbor not in visited:
                heapq.heappush(edges, (w, v, neighbor))

    return mst_edges, total_weight

def kruskal(edges, vertices):
    """
    Kruskal最小生成树算法
    :param edges: 边列表 [(权重, 顶点1, 顶点2), ...]
    :param vertices: 顶点集合
    :return: MST边列表, 总权重
    """
    # 并查集
    parent = {v: v for v in vertices}
    rank = {v: 0 for v in vertices}

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True

    # 按权重排序
    edges.sort()

    mst_edges = []
    total_weight = 0

    for weight, u, v in edges:
        if union(u, v):
            mst_edges.append((u, v, weight))
            total_weight += weight
            if len(mst_edges) == len(vertices) - 1:
                break

    return mst_edges, total_weight
```

---

## 3. 网络流问题 (Network Flow Problem)

### 算法介绍

网络流问题研究在网络中从源点到汇点的最大流量。

#### 3.1 最大流问题

**基本概念**:
- **容量**:每条边的最大流量限制$c(u,v)$
- **流量**:每条边的实际流量$f(u,v)$
- **源点**:流出的起点$s$
- **汇点**:流入的终点$t$

**流量守恒**:
$$
\sum_{v} f(v, u) = \sum_{v} f(u, v), \quad \forall u \neq s, t
$$

**容量限制**:
$$
0 \leq f(u, v) \leq c(u, v)
$$

#### 3.2 Ford-Fulkerson算法

通过寻找增广路径增加流量,直到不存在增广路径。

**残差网络**:
$$
c_f(u, v) = \begin{cases}
c(u, v) - f(u, v), & \text{如果}(u, v) \in E \\
f(v, u), & \text{如果}(v, u) \in E \\
0, & \text{否则}
\end{cases}
$$

#### 3.3 Edmonds-Karp算法

Ford-Fulkerson的实现,使用BFS找增广路径。

**时间复杂度**:$O(VE^2)$

#### 3.4 Dinic算法

使用层次图和多路增广,效率更高。

**时间复杂度**:$O(V^2E)$

#### 3.5 最小费用最大流

在最大流的基础上使总费用最小。

**目标**:
$$
\min \sum_{(u,v) \in E} f(u, v) \cdot cost(u, v)
$$

### 适用范围

| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 交通流 | 城市交通流量 | 通行能力 |
| 物流配送 | 货物运输调度 | 运输量最大化 |
| 通信网络 | 数据传输 | 带宽分配 |
| 电力系统 | 电力调配 | 输电容量 |
| 项目调度 | 任务分配 | 资源分配 |
| 匹配问题 | 二分图匹配 | 转化为最大流 |

### 可视化图表类型

- **网络流图**:流量/容量标注
- **残差网络图**:残差容量可视化
- **增广路径图**:增广路径高亮
- **流量分配图**:流量分配情况
- **瓶颈分析图**:瓶颈边识别

### 关键文献

| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Maximal Flow Through a Network | Ford & Fulkerson | 1956 | Canadian Journal of Mathematics |
| A new approach to the maximum flow problem | Edmonds & Karp | 1972 | Journal of the ACM |
| An algorithm for fast calculation of the best route | Dinic | 1970 | Soviet Math. Dokl. |

### 代码实现要点

```python
from collections import deque

class Edge:
    def __init__(self, to, rev, capacity, cost=0):
        self.to = to
        self.rev = rev
        self.capacity = capacity
        self.cost = cost

class MaxFlow:
    def __init__(self, n):
        self.n = n
        self.graph = [[] for _ in range(n)]

    def add_edge(self, fr, to, cap, cost=0):
        """添加边"""
        forward = Edge(to, len(self.graph[to]), cap, cost)
        backward = Edge(fr, len(self.graph[fr]) - 1, 0, -cost)
        self.graph[fr].append(forward)
        self.graph[to].append(backward)

    def max_flow_edmonds_karp(self, s, t):
        """Edmonds-Karp最大流"""
        flow = 0
        n = len(self.graph)

        while True:
            # BFS寻找增广路径
            level = [-1] * n
            queue = deque([s])
            level[s] = 0
            parent = [(-1, -1)] * n

            while queue:
                v = queue.popleft()
                for i, edge in enumerate(self.graph[v]):
                    if edge.capacity > 0 and level[edge.to] < 0:
                        level[edge.to] = level[v] + 1
                        parent[edge.to] = (v, i)
                        queue.append(edge.to)

            if level[t] < 0:
                break

            # 计算增广量
            min_cap = float('inf')
            v = t
            while v != s:
                p, i = parent[v]
                edge = self.graph[p][i]
                min_cap = min(min_cap, edge.capacity)
                v = p

            # 更新流量
            v = t
            while v != s:
                p, i = parent[v]
                edge = self.graph[p][i]
                edge.capacity -= min_cap
                self.graph[v][edge.rev].capacity += min_cap
                v = p

            flow += min_cap

        return flow

    def min_cost_max_flow(self, s, t, maxf=float('inf')):
        """最小费用最大流(Successive Shortest Path算法)"""
        n = len(self.graph)
        res = 0
        h = [0] * n  # 势能
        prevv = [0] * n
        preve = [0] * n
        flow = 0

        while flow < maxf:
            # Dijkstra算法
            dist = [float('inf')] * n
            dist[s] = 0
            in_queue = [False] * n
            queue = deque([s])
            in_queue[s] = True

            while queue:
                v = queue.popleft()
                in_queue[v] = False
                for i, edge in enumerate(self.graph[v]):
                    if edge.capacity > 0 and dist[edge.to] > dist[v] + edge.cost + h[v] - h[edge.to]:
                        dist[edge.to] = dist[v] + edge.cost + h[v] - h[edge.to]
                        prevv[edge.to] = v
                        preve[edge.to] = i
                        if not in_queue[edge.to]:
                            queue.append(edge.to)
                            in_queue[edge.to] = True

            if dist[t] == float('inf'):
                break

            for v in range(n):
                if dist[v] < float('inf'):
                    h[v] += dist[v]

            # 计算增广量
            d = maxf - flow
            v = t
            while v != s:
                d = min(d, self.graph[prevv[v]][preve[v]].capacity)
                v = prevv[v]

            flow += d
            res += d * h[t]

            # 更新残差网络
            v = t
            while v != s:
                edge = self.graph[prevv[v]][preve[v]]
                edge.capacity -= d
                self.graph[v][edge.rev].capacity += d
                v = prevv[v]

        return flow, res
```

---

## 4. 关键路径问题 (Critical Path Method, CPM)

### 算法介绍

关键路径法用于项目管理中确定项目完成的最短时间和关键活动。

**基本概念**:
- **活动**:项目中的任务
- **持续时间**:活动需要的时间
- **最早开始时间(ES)**:活动可以开始的最早时间
- **最早完成时间(EF)**:$EF = ES + 持续时间$
- **最晚完成时间(LF)**:活动必须完成的最晚时间
- **最晚开始时间(LS)**:$LS = LF - 持续时间$
- **总时差**:$TF = LS - ES = LF - EF$

**关键路径**:总时差为0的活动组成的路径。

### 算法步骤

#### 正向计算(最早时间)
1. $ES_{start} = 0$
2. $EF_i = ES_i + 持续时间_i$
3. $ES_j = \max\{EF_i\}$(所有前驱活动$i$)

#### 反向计算(最晚时间)
1. $LF_{end} = EF_{end}$
2. $LS_i = LF_i - 持续时间_i$
3. $LF_i = \min\{LS_j\}$(所有后继活动$j$)

### 适用范围

| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 项目管理 | 工程项目进度 | 活动依赖关系 |
| 生产调度 | 车间作业调度 | 工序约束 |
| 软件开发 | 软件项目计划 | 任务依赖 |
| 建筑工程 | 建筑进度规划 | 工序安排 |
| 活动策划 | 大型活动筹备 | 时间管理 |

### 可视化图表类型

- **网络图**:活动依赖关系图
- **甘特图**:活动时间安排
- **关键路径图**:关键路径高亮
- **时差分析图**:各活动时差
- **PERT图**:不确定时间的项目管理

### 关键文献

| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Critical-Path Planning and Scheduling | Kelley & Walker | 1959 | Proceedings of the Eastern Joint Computer Conference |

### 代码实现要点

```python
import networkx as nx
import matplotlib.pyplot as plt

def critical_path_method(activities):
    """
    关键路径法
    :param activities: 活动列表 {活动名: {'duration': 持续时间, 'predecessors': [前驱活动]}}
    :return: 关键路径, 各活动时间参数
    """
    # 创建有向图
    G = nx.DiGraph()

    # 添加活动节点
    for activity, data in activities.items():
        G.add_node(activity, duration=data['duration'])

    # 添加依赖关系边
    for activity, data in activities.items():
        for pred in data['predecessors']:
            G.add_edge(pred, activity)

    # 拓扑排序
    topo_order = list(nx.topological_sort(G))

    # 正向计算(最早时间)
    ES = {}
    EF = {}
    for activity in topo_order:
        duration = activities[activity]['duration']
        predecessors = list(G.predecessors(activity))
        if predecessors:
            ES[activity] = max(EF[pred] for pred in predecessors)
        else:
            ES[activity] = 0
        EF[activity] = ES[activity] + duration

    # 反向计算(最晚时间)
    LF = {activity: EF[activity] for activity in reversed(topo_order)}
    LS = {}

    for activity in reversed(topo_order):
        duration = activities[activity]['duration']
        successors = list(G.successors(activity))
        if successors:
            LF[activity] = min(LS[succ] for succ in successors)
        LS[activity] = LF[activity] - duration

    # 计算总时差
    TF = {activity: LS[activity] - ES[activity] for activity in activities}

    # 找出关键路径(时差为0的活动)
    critical_activities = [act for act in activities if TF[act] == 0]

    # 构建关键路径
    critical_path = []
    for act in critical_activities:
        if not list(G.predecessors(act)):  # 起点
            path = [act]
            current = act
            while list(G.successors(current)):
                for succ in G.successors(current):
                    if succ in critical_activities:
                        path.append(succ)
                        current = succ
                        break
            if len(path) > len(critical_path):
                critical_path = path

    # 汇总时间参数
    time_params = {}
    for activity in activities:
        time_params[activity] = {
            'ES': ES[activity],
            'EF': EF[activity],
            'LS': LS[activity],
            'LF': LF[activity],
            'TF': TF[activity]
        }

    return critical_path, time_params
```

---

## 5. 欧拉路径与哈密顿路径

### 算法介绍

#### 5.1 欧拉路径

**定义**:经过图中每条边恰好一次的路径。

**存在条件**:
- 欧拉回路:所有顶点度数为偶数
- 欧拉路径:恰好两个顶点度数为奇数

**Fleury算法**:
1. 选择起点(度数为奇数的顶点或任意顶点)
2. 沿边前进,避免走桥边(除非无其他选择)
3. 直到回到起点(回路)或无法继续

**Hierholzer算法**:
1. 从任意顶点开始,沿边前进回到起点形成回路
2. 若有未访问边,将回路分解并合并

#### 5.2 哈密顿路径

**定义**:经过图中每个顶点恰好一次的路径。

**哈密顿回路**:起点和终点相同的哈密顿路径。

**NP完全问题**:没有多项式时间算法。

**求解方法**:
- 回溯法(小规模)
- 动态规划(中等规模)
- 启式算法(大规模)

### 适用范围

| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 路线规划 | 邮递员送信 | 中国邮递员问题 |
| 巡回路线 | 巡检路线 | 经过每条边 |
| 环球旅行 | 旅游规划 | 经过每个城市 |
| 基因测序 | DNA片段组装 | 超级路径问题 |
| 电路设计 | PCB布线 | 笔画问题 |

### 可视化图表类型

- **路径图**:欧拉/哈密顿路径可视化
- **度数分布图**:顶点度数分布
- **搜索树图**:回溯搜索过程
- **对比图**:欧拉路径vs哈密顿路径

### 关键文献

| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Solutio problematis ad geometriam situs pertinentis | Euler | 1736 | Commentarii Academiae |
| On the Hamiltonian Game | Hamilton | 1857 | Icosian Game |

### 代码实现要点

```python
def has_eulerian_path(graph):
    """判断是否存在欧拉路径"""
    odd_degree_count = 0
    for vertex in graph:
        if len(graph[vertex]) % 2 != 0:
            odd_degree_count += 1
    return odd_degree_count == 0 or odd_degree_count == 2

def hierholzer_eulerian_circuit(graph, start):
    """Hierholzer算法找欧拉回路"""
    circuit = []
    stack = [start]
    current_path = {vertex: list(neighbors) for vertex, neighbors in graph.items()}

    while stack:
        current = stack[-1]
        if current_path[current]:
            next_vertex = current_path[current].pop()
            stack.append(next_vertex)
        else:
            circuit.append(stack.pop())

    return circuit[::-1]

def hamiltonian_path(graph):
    """回溯法找哈密顿路径"""
    vertices = list(graph.keys())
    n = len(vertices)
    path = []
    visited = set()

    def backtrack(current):
        path.append(current)
        visited.add(current)

        if len(path) == n:
            return True

        for neighbor in graph[current]:
            if neighbor not in visited:
                if backtrack(neighbor):
                    return True

        visited.remove(current)
        path.pop()
        return False

    for start in vertices:
        if backtrack(start):
            return path

    return None

def tsp_dynamic_programming(dist_matrix):
    """
    TSP 动态规划(Held-Karp),精确解,适用 n ≤ 20
    :param dist_matrix: 距离矩阵 shape (n,n)
    :return: 最短路径长度, 路径
    """
    n = len(dist_matrix)
    # dp[mask][i]: 已访问 mask 集合、最后在 i 的最短长度
    dp = [[float('inf')] * n for _ in range(1 << n)]
    parent = [[None] * n for _ in range(1 << n)]
    dp[1][0] = 0  # 从城市 0 出发

    for mask in range(1 << n):
        for i in range(n):
            if not (mask >> i) & 1 or dp[mask][i] == float('inf'):
                continue
            for j in range(n):
                if (mask >> j) & 1:
                    continue
                new_mask = mask | (1 << j)
                nd = dp[mask][i] + dist_matrix[i][j]
                if nd < dp[new_mask][j]:
                    dp[new_mask][j] = nd
                    parent[new_mask][j] = i

    full = (1 << n) - 1
    best = min(dp[full][i] + dist_matrix[i][0] for i in range(1, n))
    last_i = min(range(1, n), key=lambda i: dp[full][i] + dist_matrix[i][0])
    # 回溯路径:从最后到达的城市 last_i 倒推到起点 0
    path = []
    mask, cur = full, last_i
    while cur is not None:
        path.append(cur)
        prev = parent[mask][cur]
        mask ^= (1 << cur)
        cur = prev
    path = path[::-1]  # 现在是 [0, ..., last_i]
    path.append(0)  # 回到起点,形成回路
    return best, path

def tsp_nearest_neighbor(dist_matrix):
    """
    TSP 最近邻启发式,快速近似解,适用大规模
    :param dist_matrix: 距离矩阵 shape (n,n)
    :return: 近似最短长度, 路径
    """
    n = len(dist_matrix)
    visited = [False] * n
    visited[0] = True
    path = [0]
    cur = 0
    total = 0.0
    for _ in range(n - 1):
        # 选最近的未访问城市
        nxt = min((j for j in range(n) if not visited[j]),
                  key=lambda j: dist_matrix[cur][j])
        total += dist_matrix[cur][nxt]
        visited[nxt] = True
        path.append(nxt)
        cur = nxt
    total += dist_matrix[cur][0]
    path.append(0)
    return total, path

def chinese_postman(graph):
    """
    中国邮递员问题(边邮路,把奇数度顶点对加边后求欧拉回路)
    :param graph: 邻接表 {u: [(v, weight), ...]},要求连通图
    :return: 最短邮路长度, 是否可直接欧拉回路
    """
    vertices = list(graph.keys())
    odd = [v for v in vertices if len(graph[v]) % 2 != 0]
    if len(odd) == 0:
        return 0.0, True  # 已是欧拉图
    if len(odd) % 2 != 0:
        raise ValueError("奇数度顶点数必须为偶数(握手定理),输入图不合法")

    # 用 Floyd 求奇数度顶点间最短距离,做最小权完美匹配(简单贪心近似)
    dist = {v: {u: float('inf') for u in vertices} for v in vertices}
    for v in vertices:
        dist[v][v] = 0
        for u, w in graph[v]:
            dist[v][u] = min(dist[v][u], w)
    for k in vertices:
        for i in vertices:
            for j in vertices:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    # 贪心匹配奇数度顶点(近似解;精确可用最小权完美匹配)
    matched = set()
    extra = 0.0
    for i in range(len(odd)):
        if odd[i] in matched:
            continue
        best_j, best_d = None, float('inf')
        for j in range(i + 1, len(odd)):
            if odd[j] in matched:
                continue
            d = dist[odd[i]][odd[j]]
            if d < best_d:
                best_j, best_d = odd[j], d
        matched.add(odd[i]); matched.add(best_j)
        extra += best_d

    base = sum(w for u in graph for _, w in graph[u]) / 2  # 原边总长
    return base + extra, False

def astar_search(graph, start, goal, heuristic):
    """
    A* 搜索(有启发函数的最短路径)
    :param graph: 邻接表 {u: [(v, weight), ...]}
    :param start: 起点
    :param goal: 终点
    :param heuristic: 启发函数 h(node) → 到目标估计值(可采纳时最优)
    :return: 路径列表, 总代价
    """
    import heapq
    open_set = [(heuristic(start), 0, start, [start])]
    visited = set()
    while open_set:
        f, g, node, path = heapq.heappop(open_set)
        if node in visited:
            continue
        visited.add(node)
        if node == goal:
            return path, g
        for nxt, w in graph[node]:
            if nxt not in visited:
                heapq.heappush(open_set, (g + w + heuristic(nxt), g + w, nxt, path + [nxt]))
    return None, float('inf')
```

---

## 6. 匹配问题

### 算法介绍

匹配是指图中一组没有公共顶点的边。

#### 6.1 二分图最大匹配

**定义**:在二分图中找边数最多的匹配。

**匈牙利算法**:
1. 初始匹配为空
2. 寻找增广路径
3. 沿增广路径增加匹配
4. 重复直到无增广路径

**时间复杂度**:$O(VE)$

#### 6.2 最大权匹配

在带权图中找总权重最大的匹配。

**KM算法**(Kuhn-Munkres):
- 适用于完全二分图
- 使用顶标和相等子图
- 时间复杂度:$O(V^3)$

### 适用范围

| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 任务分配 | 人员分配任务 | 二分图匹配 |
| 婚姻匹配 | 男女婚配 | 稳定匹配 |
| 课程排课 | 教师课程分配 | 匹配问题 |
| 器官移植 | 供体受体匹配 | 权重匹配 |
| 运输调度 | 司机车辆分配 | 最大权匹配 |

### 可视化图表类型

- **二分图**:二分图结构可视化
- **匹配边图**:匹配边高亮
- **增广路径图**:增广路径显示
- **权重标注图**:边的权重标注

### 关键文献

| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| The Hungarian Method for the assignment problem | Kuhn | 1955 | Naval Research Logistics Quarterly |
| Algorithms for the assignment and transportation problems | Munkres | 1957 | Journal of the SIAM |

### 代码实现要点

```python
def hungarian_algorithm(cost_matrix):
    """
    匈牙利算法解决指派问题
    :param cost_matrix: 成本矩阵
    :return: 最小成本匹配
    """
    n = len(cost_matrix)
    cost_matrix = [row[:] for row in cost_matrix]  # 深拷贝

    # 初始化
    u = [0] * (n + 1)
    v = [0] * (n + 1)
    matching = [0] * (n + 1)

    # 行约减
    for i in range(1, n + 1):
        u[i] = min(cost_matrix[i - 1])

    # 列约减
    for j in range(1, n + 1):
        v[j] = min(cost_matrix[i - 1][j - 1] - u[i] for i in range(1, n + 1))

    # 寻找匹配
    for i in range(1, n + 1):
        while True:
            # 构建相等子图
            used = [False] * (n + 1)
            min_slack = [float('inf')] * (n + 1)
            parent = [0] * (n + 1)

            def dfs(x):
                used[x] = True
                for y in range(1, n + 1):
                    if not used[y]:
                        slack = cost_matrix[x - 1][y - 1] - u[x] - v[y]
                        if slack < min_slack[y]:
                            min_slack[y] = slack
                            parent[y] = x
                        if matching[y] == 0 or dfs(matching[y]):
                            matching[y] = x
                            return True
                return False

            if dfs(i):
                break

            # 更新顶标
            delta = min(min_slack[y] for y in range(1, n + 1) if not used[y])
            for x in range(1, n + 1):
                if used[x]:
                    u[x] += delta
            for y in range(1, n + 1):
                if used[y]:
                    v[y] -= delta

    # 构建匹配结果
    result = []
    for j in range(1, n + 1):
        if matching[j] != 0:
            result.append((matching[j] - 1, j - 1))

    total_cost = sum(cost_matrix[i][j] for i, j in result)

    return total_cost, [(i, j) for i, j in result]
```

---

## 图论算法选择指南

### 按问题类型选择

| 问题类型 | 推荐算法 | 说明 |
|---------|---------|------|
| 两点最短路径 | Dijkstra | 非负权图 |
| 含负权最短路 | Bellman-Ford | 可检测负权回路 |
| 全源最短路 | Floyd-Warshall | 稠密图 |
| 连接所有顶点最小成本 | Prim/Kruskal | 最小生成树 |
| 最大传输能力 | 最大流算法 | Edmonds-Karp/Dinic |
| 最小费用传输 | 最小费用最大流 | 考虑费用 |
| 项目最短完成时间 | 关键路径法 | CPM/PERT |
| 经过所有点/边 | 欧拉/哈密顿路径 | 特殊路径 |
| 两两配对 | 二分图匹配 | 匈牙利算法 |

### 按图的特征选择

| 图特征 | 推荐算法 |
|---------|---------|
| 稀疏图 | 邻接表存储、Kruskal |
| 稠密图 | 邻接矩阵存储、Prim、Floyd-Warshall |
| 非负权 | Dijkstra |
| 含负权 | Bellman-Ford |
| 有向图 | Dijkstra、Bellman-Ford、网络流 |
| 无向图 | Prim、Kruskal |
| 树结构 | DFS、BFS |
| 二分图 | 匈牙利算法、最大流 |

### 按数据规模选择

| 规模 | 推荐算法 |
|------|---------|
| 小规模(<100顶点) | Floyd-Warshall、暴力搜索 |
| 中规模(100-10000) | Dijkstra、Prim、Edmonds-Karp |
| 大规模(>10000) | 优化的Dijkstra、A*算法 |

---

## 参考文献

1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. *Numerische Mathematik*, 1(1), 269-271.
2. Floyd, R. W. (1962). Algorithm 97: shortest path. *Communications of the ACM*, 5(6), 345.
3. Prim, R. C. (1957). Shortest connection networks and some generalizations. *Bell System Technical Journal*, 36(6), 1389-1401.
4. Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. *Proceedings of the American Mathematical Society*, 7(1), 48-50.
5. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. *Canadian Journal of Mathematics*, 8(5), 399-404.
6. Edmonds, J., & Karp, R. M. (1972). Theoretical improvements in algorithmic efficiency for network flow problems. *Journal of the ACM*, 19(2), 248-264.
7. Kelley, J. E., & Walker, M. R. (1959). Critical-path planning and scheduling. *Proceedings of the Eastern Joint Computer Conference*, 160-173.
8. Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. *Commentarii Academiae Scientiarum Imperialis Petropolitanae*, 8, 128-140.
9. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. *Naval Research Logistics Quarterly*, 2(1-2), 83-97.
10. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). *Introduction to Algorithms* (3rd ed.). MIT Press.
reverse-engineer-anythingmorluto/reaReverse engineer native, managed, Electron/JavaScript, packaged, firmware, and browser targets with REA, and build agent environments (AgentEnv bundles) of web applications from a live instance or a capture, and of Linux desktop apps with a task from a request. Use shipped-artifact or requested runtime evidence to explain features, compare versions, decompile code, or guide a reconstruction. Skip REA for ordinary source-repository architecture analysis.Stars: 472kUpdated Claude CodeCodexVerifiedInstall
diagnosing-superpowersobra/superpowersUse when a superpowers session went wrong and your human partner wants to know why — repeated work, ignored plans, stumbles, poor results, a skill that didn't fire, "it took too long", "why is it so expensive", "what is it doing" — or wants to build a bug report for the superpowers maintainers, for the current session or a past one identified by id or path, on any harness.Stars: 323kUpdated Claude CodeCodexVerifiedInstall
dispatching-parallel-agentsobra/superpowersUse when facing 2+ independent tasks that can be worked on without shared state or sequential dependenciesStars: 323kUpdated Claude CodeCodexVerifiedInstall
executing-plansobra/superpowersUse when executing an implementation plan in the current session as the implementer yourself — your human partner chose inline execution, or no subagent tool is availableStars: 323kUpdated Claude CodeCodexVerifiedInstall