拓扑排序

只能应用于有向图

1. 一个有向图，如果图中有入度为 0 的点（必要条件），就把这个点删掉，同时也删掉这个点所连的边。
2. 一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。 不能够进行拓扑排序的图的充分条件：

• 存在环

可以证明 有向无环图 一定能够进行 拓扑排序，有向无环图也被称为 拓扑图

一个 拓扑图 至少存在一个 入度为 0 的点

拓扑序列

满足拓扑排序的一个序列

应用场景

• 拓扑排序的重要应用：判断 AOV 网中是否存在环。判定方法：对有向图构造拓扑排序，如果所有顶点都在它的拓扑序列中，则该 AOV 网必定不存在环。

算法过程

1. 在图中找出所有入度为 0 的点，加入队列 queue
   1. 枚举 队列中的 所有点 ：顶点 t = queue.head() ==> 拆点操作，拆掉这个点和所有相连的边
   2. 枚举 顶点 t 的所有出边： t -> j
      1. 删掉 t->
2. 重复上面的操作，直到所有点都已拆除；
3. 最后，得到的拓扑序列中已经包含了所有点（除了环中的所有点，因为环中的所有点 入度都不为 0 ） 拓扑排序实际上是 $BFS$ 的一种特殊情况，每次加入队列的点是入度为 0 的点，加入队列后拆掉相邻的边；记录已经拆掉的点

代码实现

AcWing 848. 有向图的拓扑序列 (opens new window)

#include <iostream>
#include<cstring>

using namespace std;

const int N  = 1e5+10;

int h[N], e[N], ne[N], idx = 0; // 初始化图
int d[N], q[N]; // d[N] 入度数组 ； q[N]： bfs队列
int n, m;

void add(int a, int b){ // 加边
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort(){ // 拓扑排序；返回是否是拓扑图
    int hh = 0, tt = -1;
    for (int i = 1; i< n; i++){ // 入度为 0 的顶点 入队
        if (!d[i]) q[++tt] = i;
    }

    while (hh <= tt){
        int t = q[hh++];		// 顶点出队
        for (int i = h[t]; i!=-1; i = ne[i]){ // 枚举 顶点为起点的边
            int j = e[i];			// 边的终点
            d[j]--;				// 拆边
            if (!d[j]) {	// 入度为 0  入队
                q[++tt] = j;
            }
        }
    }
    return tt == n-1; 	// 所有顶点入队 ，则为拓扑图
}
int main(){
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i =0; i< m; i++){
        int a,b;
        cin >> a>> b;
        add(a, b); // 图 加 边
        d[b]++;	// 入度 +1
    }

    if (topsort()){
        for (int i =0; i< n; i++){ // 队列中的顺序就是 一个合法的拓扑序列
            cout << q[i] << " ";
        }
        cout << endl;
    }else {
        cout << -1 << endl;
    }
    return 0;
}