「数据结构详解·十二」有向无环图 & 拓扑排序

大家好，欢迎来到IT知识分享网。

• 「数据结构详解·一」树的初步
• 「数据结构详解·二」二叉树的初步
• 「数据结构详解·三」栈
• 「数据结构详解·四」队列
• 「数据结构详解·五」链表
• 「数据结构详解·六」哈希表
• 「数据结构详解·七」并查集的初步
• 「数据结构详解·八」带权并查集 & 扩展域并查集
• 「数据结构详解·九」图的初步
• 「数据结构详解·十」双端队列 & 单调队列的初步
• 「数据结构详解·十一」单调栈
• 「数据结构详解·十二」有向无环图 & 拓扑排序

如果你还没有学过图的基本概念，前往 「数据结构详解·九」图的初步。

1. 有向无环图的概念

有向无环图(Directed acyclic graph, DAG)，字面意思，就是一个没有环的有向图。
比如下图就是一个 DAG：

而下图就不是一个 DAG，因为它存在环 $1-3-5-1$：

于是，我们就发现，只有父亲指向儿子的边的树是一个 DAG。

DAG 作为特殊的有向图，在各方面都有很重要的作用。
比如，凡是可以进行 dp（动态规划）的数据，其承接关系一定是一个 DAG。

DAG 有一个非常重要的性质：一个 DAG 中，必然存在至少一个顶点的入度为 $0$，至少一个顶点的出度为 $0$。
下面的拓扑排序便利用了这个性质。
（附：下文中，${\text{din}}_i$ 表示节点 $i$ 的入度，${\text{dout}}_i$ 表示节点 i 的出度）

2. 拓扑排序的概念及实现

拓扑排序(topological-sort, toposort, topsort)，是对一个 DAG $G$，将 $G$ 中所有所有顶点排成一个线性序列，使得图中任意一对顶点 $u,v$，若边 $u\to v\in E(G)$，则 $u$ 在线性序列中出现在 $v$ 之前。所以说，它不是对数据的一种排序算法。

• 取出队首节点 $x$，将所有以它为起点的边删去，也就是对于所有存在的边 $x\to i$，进行 din[i]--；
• 对于每个进行 din[i]-- 的 $i$，看它操作之后的 ${\text{din}}_i$ 是否为 $0$，是则加入队列，然后重复上面的操作。

可以看出来，操作其实就是对每一条有向边 $u\to v$，保证 $u$ 在前 $v$ 在后即可。
最后我们排序出来的一种可能的方案：

参考代码：

#include<bits/stdc++.h> using namespace std; vector<int>g[105]; queue<int>q; int n,din[105]; void toposort() { 
     for(int i=1;i<=n;i++) { 
     if(din[i]) continue; q.push(i); } while(!q.empty()) { 
     int x=q.front(); q.pop(); cout<<x<<' '; for(auto i:g[x]) { 
     if(!--din[i]) q.push(i); } } } int main() { 
     cin>>n; for(int i=1;i<=n;i++) { 
     int x; cin>>x; while(x) { 
     din[x]++; g[i].push_back(x); cin>>x; } } toposort(); return 0; } 

3. 例题详解

3-1. P4017 最大食物链计数

容易发现，本题需要求的就是一个 DAG 中节点对 $(u,v)$ 满足存在从 $u$ 到 $v$ 的路径且 ${\text{din}}_u={\text{dout}}_v=0$。
而根据我们小学学过的加法原理，DAG 中到节点 $p$ 的路径数量一定是其入边上的节点路径数之和。
于是我们就可以拓扑排序的时候 dp。记 $f_i$ 表示到节点 $i$ 的路径数量，状态转移方程为 $f_i=\sum _{x\to i\in E(G)}{f}_x$，而最后答案就是所有出度为 $0$ 的节点路径数之和，即 $\text{ans}=\sum _{{\text{dout}}_i=0}{f}_i$。
参考代码：

#include<bits/stdc++.h> #define mod  using namespace std; vector<int>a[5005]; queue<int>q; int n,m,din[5005],dout[5005],f[5005]; void toposort() { 
     while(!q.empty()) { 
     int x=q.front(); q.pop(); for(auto i:a[x]) { 
     f[i]=(f[i]+f[x])%mod; if(!--din[i]) q.push(i); } } } int main() { 
     cin>>n>>m; while(m--) { 
     int x,y; cin>>x>>y; a[x].push_back(y); dout[x]++; din[y]++; } for(int i=1;i<=n;i++) { 
     if(!din[i]) { 
     f[i]=1; q.push(i); } } toposort(); int ans=0; for(int i=1;i<=n;i++) { 
     if(!dout[i]) ans=(ans+f[i])%mod; } cout<<ans; return 0; } 

3-2. P1807 最长路

发现我们输入的有向边满足 $u<v$。
于是可以想到拓扑排序时进行类似 spfa 的松弛操作。
代码留给读者自行思考。

4. 巩固练习

• 例题 12-3-2 P1807 最长路
• P1347 排序
• P1983 [NOIP2013 普及组] 车站分级
• P3183 [HAOI2016] 食物链