有向无环图可以用来表示各种事物的顺序，比如工作顺序。一些事情必须在另一些事情完成之后才能开始进行。那么，为了获得正确的工作顺序（一件事情开始之前，必须保证它的前置条件全部满足），就需要用到拓扑排序。
拓扑排序其实就是在有向无环图中，只要存在边(u,v)，那就让u排在v前面。
我们可以通过广度优先搜索或者深度优先搜索来实现拓扑排序。
广度优先的思路就是对每个入度为0的且未被访问过的节点进行广度优先搜索。
在搜索过程中，只要搜索了u与v之间的边，那就将v的入度减1，相当于删除边的操作。入度为零就代表着它的前置条件已经完全满足。一个节点只有当其入度为0且未被访问过，才对其进行广度优先搜索。
下面是通过bfs拓扑排序的伪代码
利用DFS进行拓扑排序的思路相对简单，就是循环以当前仍未搜索的节点为起点，进行dfs，然后逆序把节点id存入列表中。但是，对于大规模的图来说，深度优先搜索很容易栈溢出，并且由于递归调用有开销，所以，采用BFS会更好。
对于题目 GRL_4_B ，采用BFS的AC代码如下
代码语言：javascript复制#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAXV 10005
vector<int> vec[MAXV];
vector<int> ans;
int v, e;
int indeg[MAXV] = {0};
bool vis[MAXV] = {false};
void bfs(int u)
{
queue<int>q;
vis[u] = true;
q.push(u);
while(!q.empty())
{
int t = q.front();
q.pop();
ans.push_back(t);
for(int x:vec[t])
{
indeg[x]--;
if(indeg[x]==0&&vis[x]==false)
{
q.push(x);
vis[x] = true;
}
}
}
}
void solve()
{
for (int i = 0; i < v; i)
{
if (indeg[i] == 0 && vis[i] == false)
{
bfs(i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> v >> e;
int s, t;
for (int i = 0; i < e; i)
{
cin >> s >> t;
vec[s].push_back(t);
indeg[t] ;
}
solve();
for(int x:ans)
{
cout<<x<<endl;
}
}转载请注明来源：https://www.longjin666.top/?p=762
