拓扑排序

简介

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）

AOV网（Activity On Vertex Network，用顶点表示活动的网）：用DAG表示一个工程，顶点表示活动，有向边$<V_i,V_j>$表示活动$V_i$必须先于$V_j$进行。

拓扑排序是一个有向无环图(DAG)的所有顶点的线性序列，且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

实现：

1. 从AOV网中选择一个没有前驱（入度为0）的顶点并输出；
2. 从网中删除该顶点和所有以它为起点的有向边；
3. 重复1和2直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（说明有回路）。

逆拓扑序：

1. 从AOV网中选择一个没有后继（出度为0）的顶点并输出；
2. 从网中删除该顶点和所有以它为终点的有向边；
3. 重复1和2直到当前的AOV网为空。

思路：

1. 用一种容器（比如栈，队列，集合）维护当前所有入度为0的点。
2. 每次从容器中取出一个点，删掉他和他的出边，这可能导致一些点入度为0，将新的入度为0的点加入容器。

代码

邻接表：时间复杂度 $O(n+m)$, $n$ 表示点数，$m$ 表示边数

邻接矩阵：时间复杂度 $O(n^2)$

也可以使用dfs实现

const int maxn = 1e5 + 5;
const int maxe = 2e5 + 5;

int n;      // 点的数量
int h[maxn], e[maxe], ne[maxe], idx;  // 邻接表存储所有边
int d[maxn];//每个点的入度 
int print[maxn];//拓扑序列 

//加边
void add(int x, int y) {
    e[idx] = y; // 这样堆中会有很多冗余的点，但是在弹出的时候还是会弹出最小值2+x（x为之前确定的最短路径），并
    ne[idx] = h[x]; // 标记st为true，所以下一次弹出3+x会continue不会向下执行。
    h[x] = idx++;
    d[y]++;//入度 
}
//拓扑排序 
bool topsort() {
    stack<int> s;//存储入度为0的点 

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])//将所有入度为0的点入栈 
            s.push(i);
	
	int cnt = 0;//记录当前已经输出的顶点数 
    while (!s.empty()) {//栈不空，存在入度为0的顶点 
        int t = s.top();
        s.pop();
        print[cnt++] = t; 

        for (int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if (-- d[j] == 0)
                s.push(j);
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return cnt == n;
}

练习