有向图的拓扑序列
一、简介
1、概念
拓扑序列是顶点活动网中将活动按发生的先后次序进行的一种排列。 拓扑排序，是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。
2、简单举例：
这样一个有向无环图的拓扑序列是1、2、3。
可以证明一个有向无环图一定存在拓扑序列，所以有向无环图又被称为拓扑图。
3、入度与出度
入度是指有多少条边指向该结点，出度是该结点有多少条边指出。
上图为例：
入度出度102211320
二、排序
由于入度为0的点没有被任何边指向，所以任何一个入度为0的点都可以排在当前最前面的位置，所以拓扑排序的第一步为将所有入度为0的点入队。然后利用宽搜就可以达到效果了。
首先是有向图的构建：
void add(int a,int b)
{
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
然后就是排序函数：
void topsort()
{
int hh 0,tt = 0;
for(int i = 1;i <= n;i++)
if(!d[i])q[tt++] = i;//d为储存入度的数组
while(hh <= tt)
{
int t = q[hh++];
for(int i = h[t];i != -1;i++)
{
int j = e[i];
d[j]--;
if(!d[j])q[tt++] = j;
}
}
}
三、例题代码
如题：848. 有向图的拓扑序列 - AcWing题库
#include
#include
using namespace std;
const int N = 1e5+3;
int n,m;
int e[N],ne[N],h[N],idx;
int d[N],q[N];
void add(int a, int b)
{
e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool topsort()
{
int hh = 0,tt = 0;
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];
d[j]--;
if(!d[j])q[tt++] = j;
}
}
if(tt == n)return 1;//如果tt与n相等，说明该图是个有向无环图，存在拓扑序列。
return 0;
}
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]);
puts("");
}
else puts("-1");
return 0;
}