【算法】拓扑排序

一、拓扑序列的概念

首先明确一点：并不是所有图都有拓扑序列，只有有向无环图具有拓扑序列

看完拓扑序列的概念后大家就能明白这一点

一个图的所有边（x，y），将图中所有节点排成一个序列，保证所有的x都在y前面即为拓扑序列

例如下面这个图：

其中，1 2 3是拓扑序列，因为图中1在2前面，2在3前面

但是1 3 2不是拓扑序列，因为图中2在3前面，但这个序列中3在2前面

也就是说，拓扑序列的顺序一定是按照图中箭头指向的顺序排列的。因此当图中带环时一定无法得出一个拓扑序列，例如：

假设排成1 2 3，但图中3在1前面，序列中1在3前面，不符合拓扑序列的要求，所以有向带环图一定不存在拓扑序列。

因此，有向无环图也被称为拓扑图

二、求有向无环图的拓扑序列

2.1 思想

在这之前，我们首先得明白两个概念

• 入度：指向该节点的边的数量
• 出度：从该节点出发，指向其他节点的边的数量

例如这个图

没有边指向1，有两条边从1出发指向其他节点，因此1的入度为0，出度为2；

有一条边指向2，有两条边从2出发指向其他节点，因此2的入度为1，出度为2；

有三条边指向3，没有边从3出发指向其他节点，因此3的入度为3，出度为0；

有一条边指向4，有一条边从4出发指向其他节点，因此4的入度为1，出度为1

按照拓扑序列的性质，所有入度为0的节点都可以排在拓扑序列的开头，因此这个图的拓扑序列中开头为1

接下来就是求有向无环图的拓扑序列的核心操作：宽搜

第一步，将入度为0的节点入队列

第二步，每次枚举队头节点的所有出边指向的节点，将这些节点的入度减一，再将队头节点出队列。然后回到第一步。

至此，节点的出队顺序1 2 4 3就是该有向无环图的拓扑序列

所以，如果一个有向图带环，则一定存在一个时刻，图中剩余的节点无法入队，因为此时没有入度为0的节点。一个有向图不带环，任意时刻一定至少存在一个节点入度为0

2.2 例题

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

const int N = 100010;

int n, m;
int e[N], ne[N], h[N], idx;
int d[N];//节点的入度
queue<int> q;
vector<int> ans;

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

bool topsort()
{
    for(int i = 1;i <= n;i++)
        if(!d[i]) q.push(i);//将第一个入度为0的节点入队
    while(q.size())
    {
        int t = q.front();//取队头元素
        q.pop(); //出队
        ans.push_back(t);//元素加入拓扑序列
        for(int i = h[t];i != -1;i = ne[i])//遍历所有入边
        {
            int j = e[i];
            d[j]--;//将所有入点的入度-1
            if(!d[j]) q.push(j);//将入度为0的节点入队
        }
    }
    return ans.size() == n;//判断拓扑序列的元素个数是否等于节点个数
}

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]++;//记录入度
    }
    if(topsort())
    {
        for(auto i : ans)
            cout << i << " ";
        cout << endl;
    }
    else cout << -1 << endl;
    return 0;
}

完.