在一个有向图中,对所有的节点进行排序,要求没有一个节点指向它前面的节点。
先统计所有节点的入度,对于入度为0的节点就可以分离出来,然后把这个节点指向的节点的入度减一。
一直做改操作,直到所有的节点都被分离出来。
如果最后不存在入度为0的节点,那就说明有环,不存在拓扑排序,也就是很多题目的无解的情况。
下面是算法的演示过程。
下面是我以前的写法,比较好理解,但是效率低
//b[]为每个点的入度
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(b[j]==0){ //找到一个入度为0的点
ans=j;
vis[cnt++]=j;
b[j]--;
break;
}
}
for(j=1;j<=n;j++)
if(a[ans][j]) b[j]--; //与入度为0的点相连的点的入度减一
}
printf("%d",vis[0]);
for(i=1;i<cnt;i++) printf(" %d",vis[i]);
printf("\n");
下面是我现在一直以来的写法,O(V+E)。点数+边书
queue<int>q;
vector<int>edge[n];
for(int i=0;i<n;i++) //n 节点的总数
if(in[i]==0) q.push(i); //将入度为0的点入队列
vector<int>ans; //ans 为拓扑序列
while(!q.empty())
{
int p=q.front(); q.pop(); // 选一个入度为0的点,出队列
ans.push_back(p);
for(int i=0;i<edge[p].size();i++)
{
int y=edge[p][i];
in[y]--;
if(in[y]==0)
q.push(y);
}
}
if(ans.size()==n)
{
for(int i=0;i<ans.size();i++)
printf( "%d ",ans[i] );
printf("\n");
}
else printf("No Answer!\n"); // ans 中的长度与n不相等,就说明无拓扑序列
有些拓扑排序要求字典序最小什么的,那就把队列换成优先队列就好了。