利用BFS解决有向图的拓扑排序
是否存在拓扑序列判断:如果图中的任意两点有路径,只能是a点到b点,不能是b点到a点(即无环有向图)则存在拓扑序列,有向无环图一定存在至少一个拓扑序列。有向无环图因此也叫拓扑图
有向无环图一定至少有一个入度为0的结点
拓扑序列定义:拓扑序列是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
拓扑排序题的做法:先找到入度为0的点入队,再用BFS找到它们的后继结点,把后继点与队中的点的边删掉,找到新的入度为0的点入队,如果所有点都入队了,那么存在拓扑序列,结点在队中的顺序就是拓扑序列。
#include<iostream>
#include<cstring>
using namespace std;
const int N=1E5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N]; //q表示由没有入度的结点组成的队列,d表示结点的入度个数
void add(int a,int b)
{
e[idx]=b;
ne[idx]=h[a];
h[a]=idx;
++idx;
}
bool topsort()
{
int hh=1,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; //删完后如果后继结点也没入度了,则后继结点也入队
}
}
return tt==n; //当所有结点都入队了(tt==n)表示该图是拓扑图(有向无环图)那么存在拓扑序列,否则不是。
}
int main()
{
memset(h,-1,sizeof(h));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
++d[b]; //统计结点的入度
}
if(topsort())
{
for(int i=1;i<=n;i++)printf("%d ",q[i]);//因为出队顺序就是拓扑序,而且出队只是hh向后移动,所以q数组
} //的存储序列就是拓扑序
else cout<<-1;
}