拓扑排序
1. 拓扑排序的定义
拓扑排序是bfs的一个应用。拓扑排序只针对于有向图，无向图没有拓扑排序。
对于上图的序列我们可以看到如下特点：
对于图中的每一条边(x,y)，在拓扑序列中都表现为x在y之前。
如果某一个序列满足以上特点，那么这个序列就称之为拓扑序列。
需要注意的是，并不是每一个图都有拓扑序列，例如上图。上图是一个环，换句话说：只要图中有环，那么这个图是没有拓扑序列的，也就无法进行拓扑排序。
需要注意的是：可以证明，一个有向无环图，一定存在拓扑序列。一个有向无环图一定存在至少一个入度为0的点。因此，有向无环图也称为拓扑图。
注意：一个有向无环图拓扑序列是不一定唯一的。
2. 拓扑排序的思想
在了解拓扑排序之前，我们需要先了解节点度的概念。
度分为入度和出度。
1. 某个节点x的入度指的就是：有多少个节点指向x节点。
2. 某个节点x的出度指的就是：x节点分别指向了多少个节点。
具体可以看上图。
了解了度的概念之后，我们就可以阐述拓扑排序的过程了。
1. 在图中找到所有入度为0的点，进行入队。
2. 从队头依次取出元素，遍历该元素的所有出边。
3. 删掉出边，会导致该元素所邻接的点的入度-1。
重复上述过程，会导致两种结果：
1. 如果所有节点均遍历过（均入过队），那么该图存在拓扑序列，输出即可。
2. 如果仍有节点没有遍历过（有些节点无法入队），那么该图不存在拓扑序列（该图存在环），输出信息。
具体可以看上图。
3. 模板
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
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];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
4. 例题
https://www.acwing.com/problem/content/850/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100010;
int h[N],e[N],ne[N],idx = 0;
int q[N];
int hh = 0,tt = -1;
//代表每个节点的入度
int d[N];
int n,m;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topSort(){
//找到所有入度为0的点，进行入队
for(int i=1;i<=n;i++){
if(d[i] == 0){
q[++tt] = i;
}
}
while(hh <= tt){
int t = q[hh++];
for(int i=h[t];i!=-1;i=ne[i]){
//删除出边(邻接点入度-1)
d[e[i]]--;
//如果入度为0，入队
if(d[e[i]] == 0){
q[++tt] = e[i];
}
}
}
//如果所有节点均入队，那么存在拓扑序列，反之不存在
return tt == n-1;
}
int main(){
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
d[b]++;
}
//如果该图存在拓扑排序
if(topSort()){
//队列中的序列刚好就是拓扑序列
for(int i=0;i<n;i++){
printf("%d ",q[i]);
}
}else{
printf("-1");
}
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。