数据结构：有向无环图

有向无环图

资料：https://pan.quark.cn/s/43d906ddfa1b、https://pan.quark.cn/s/90ad8fba8347、https://pan.quark.cn/s/d9d72152d3cf

一、有向无环图的定义

有向无环图（Directed Acyclic Graph，简称DAG）是一类特殊的有向图，其核心特征是不存在任何有向环，即从任意顶点出发，沿着有向边遍历，无法回到该顶点。

有向无环图可形式化表示为G=(V,E)，其中V为顶点集合，E为有向边集合，且图中不存在满足v₀=vₖ且包含至少一条边的有向路径v₀→v₁→…→vₖ。

二、有向无环图的核心概念

1. 顶点的入度与出度

• 入度：以该顶点为终点的有向边数量，入度为 0 的顶点称为源点；
• 出度：以该顶点为起点的有向边数量，出度为 0 的顶点称为汇点；
• 一个DAG至少存在一个源点和一个汇点（可通过拓扑排序证明）。

2. 拓扑序列

对DAG顶点的一种线性排序，满足：若图中存在有向边<u,v>，则在序列中u一定位于v之前。

• 一个DAG的拓扑序列不唯一，例如课程依赖图可能有多种合法的学习顺序。

3. 关键路径

在带权DAG中，从源点到汇点的最长路径称为关键路径，路径上的顶点和边为关键任务，决定了整个工程的最短完成时间。

4. 可达性

对于DAG中的两个顶点u和v，若存在从u到v的有向路径，则称v可由u到达，DAG的可达性可通过拓扑排序或DFS高效判断。

三、有向无环图的存储方式

DAG的存储方式与普通有向图一致，常用以下两种：

1. 邻接矩阵

用n×n二维数组存储，adj[i][j]表示是否存在从顶点i到j的有向边，无环特性不影响存储结构，仅需保证矩阵对应的图无环。

• 优点：查询边是否存在的时间复杂度为O(1)；
• 缺点：空间复杂度为O(n²)，适合顶点数较少的DAG。

2. 邻接表

为每个顶点维护一个邻接顶点列表（带权DAG则存储（邻接顶点，权重）二元组），同时可维护入度数组，用于拓扑排序。

• 优点：空间复杂度为O(|V|+|E|)，适合稀疏DAG；
• 缺点：查询边是否存在需遍历邻接表，时间复杂度为O(outdeg(u))。

四、有向无环图的核心算法

1. 拓扑排序

拓扑排序是DAG的标志性算法，有两种经典实现方式：

（1）Kahn算法（入度贪心算法）

• 核心思想：优先选择入度为 0 的顶点加入拓扑序列，再删除该顶点的所有出边，更新邻接顶点的入度，重复此过程直到所有顶点处理完毕。
• 步骤
  1. 初始化入度数组，统计每个顶点的入度；
  2. 将所有入度为 0 的顶点加入队列；
  3. 依次取出队列顶点，加入拓扑序列，并将其邻接顶点的入度减 1，若邻接顶点入度变为 0 则加入队列；
  4. 若最终拓扑序列长度等于顶点数，则为合法DAG，否则存在环。
• 时间复杂度：O(|V|+|E|)，可同时检测图是否为DAG。

（2）DFS逆序法

• 核心思想：通过DFS遍历顶点，当顶点的所有后代顶点都处理完毕后，将其加入栈，最终栈的逆序即为拓扑序列。
• 步骤
  1. 初始化访问标记数组，遍历所有未访问顶点；
  2. 对每个顶点执行DFS，递归访问其邻接顶点；
  3. 递归回溯时将当前顶点压入栈；
  4. 遍历完成后，依次弹出栈中元素得到拓扑序列。
• 时间复杂度：O(|V|+|E|)，适合需要同时处理连通分量的场景。

2. 关键路径算法

• 核心步骤
  1. 对DAG进行拓扑排序，得到拓扑序列；
  2. 按拓扑序计算每个顶点的最早开始时间（ve）：ve[v] = max(ve[u] + weight(u,v))，其中u是v的前驱顶点；
  3. 逆拓扑序计算每个顶点的最晚开始时间（vl）：vl[u] = min(vl[v] - weight(u,v))，其中v是u的后继顶点；
  4. 若顶点的ve等于vl，则该顶点在关键路径上，对应的边为关键边。

3. 最长路径求解

在DAG中可通过拓扑排序高效求解单源最长路径：

1. 对DAG进行拓扑排序；
2. 按拓扑序松弛顶点的出边，更新后继顶点的最长距离，时间复杂度为O(|V|+|E|)。

五、有向无环图的实现示例

1. 邻接表实现（含拓扑排序与关键路径）

fromcollectionsimportdequeclassDAG:def__init__(self,num_vertices):self.num_vertices=num_vertices self.adj_list=[[]for_inrange(num_vertices)]# (v, weight)self.indegree=[0]*num_vertices# 入度数组defadd_edge(self,u,v,weight=1):"""添加有向边<u,v>，默认权重为1"""self.adj_list[u].append((v,weight))self.indegree[v]+=1deftopological_sort_kahn(self):"""Kahn算法实现拓扑排序，返回拓扑序列"""queue=deque()# 初始化入度为0的顶点foriinrange(self.num_vertices):ifself.indegree[i]==0:queue.append(i)topo_order=[]whilequeue:u=queue.popleft()topo_order.append(u)# 遍历u的出边，更新邻接顶点入度forv,_inself.adj_list[u]:self.indegree[v]-=1ifself.indegree[v]==0:queue.append(v)iflen(topo_order)!=self.num_vertices:raiseValueError("图中存在环，不是有向无环图")returntopo_orderdefcritical_path(self):"""求解关键路径，返回关键顶点列表"""try:topo_order=self.topological_sort_kahn()exceptValueErrorase:returnstr(e)# 1. 计算最早开始时间veve=[0]*self.num_verticesforuintopo_order:forv,winself.adj_list[u]:ifve[v]<ve[u]+w:ve[v]=ve[u]+w# 2. 计算最晚开始时间vlvl=[ve[-1]]*self.num_vertices# 汇点的vl等于其veforuinreversed(topo_order):forv,winself.adj_list[u]:ifvl[u]>vl[v]-w:vl[u]=vl[v]-w# 3. 筛选关键顶点（ve[u] == vl[u]）critical_vertices=[uforuinrange(self.num_vertices)ifve[u]==vl[u]]returncritical_vertices,ve[-1]# 返回关键顶点和工程最短完成时间

使用示例

# 初始化6个顶点的DAG（模拟项目任务依赖）dag=DAG(6)# 添加带权边：u->v，权重为任务耗时dag.add_edge(0,1,3)dag.add_edge(0,2,2)dag.add_edge(1,3,2)dag.add_edge(2,3,4)dag.add_edge(3,4,3)dag.add_edge(3,5,2)dag.add_edge(4,5,1)# 拓扑排序topo=dag.topological_sort_kahn()print("拓扑序列:",topo)# 输出如[0,2,1,3,4,5]# 关键路径critical_vertices,min_time=dag.critical_path()print("关键顶点:",critical_vertices)# 输出关键顶点列表print("工程最短完成时间:",min_time)# 输出总耗时

六、有向无环图的典型应用

1. 任务调度：如软件开发中的模块编译顺序、项目管理中的任务执行流程，通过拓扑排序确定合法执行顺序；
2. 课程安排：大学课程的先修依赖关系，拓扑序列为合法的选课顺序；
3. 依赖解析：包管理工具（如Maven、npm）的依赖关系分析，避免循环依赖并确定安装顺序；
4. 项目进度规划：通过关键路径算法确定项目的关键任务和最短完成时间；
5. 编译优化：编译器中表达式的求值顺序、代码的指令重排，利用DAG消除公共子表达式。