BFS—拓扑排序_bfs拓扑排序

拓扑排序是bfs的一个简单的运用，具体实现的思路如下；

先将入度为0的点放入队列，然后取出对头，用对头更新其他点的入度，如果发现新的点的入度为0，则将该点放入队列，如此循环，直到队列为空；

要注意，有环图一定无拓扑排序，所以拓扑排序的一个简单运用为判断一个图是否为有环图。

这个可以用反证法；

假定一个有环图存在拓扑排序；

入队的某一时刻，记A环中的Q点为此环中的一个入队的点，说明此刻该点的入度为0，有因为Q点是第一个入队，说明环中指向它的P点未入队，P点未入队说明Q点的入度>=1，与入队的条件和第一个入队冲突；

故有环图不存在拓扑排序；

接下来是代码和注释。

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
 
const int N = 100010;
 
struct poi {
 
	vector<int> ne;//ne中存储下一个点的下标
	int d = 0;//点的入度
 
}pos[N];
 
int p[N], fur;//存储点的拓扑排序
int n, m;//n个点，m条边
 
bool bfs() {
 
	queue<int> que;
 
	for (int i = 1; i <= n; i++) {//初始化队列，将所有入度为0的点放入队列
 
		if (!pos[i].d)
			que.push(i);
 
	}
 
 
	while (que.size()) {
 
 
		int t = que.front();
 
		p[fur++] = t;//将对头加入拓扑排序中
		que.pop();
 
		for (int i = 0; i < pos[t].ne.size(); i++) {//更新点的入度
 
			int m = pos[t].ne[i];
			pos[m].d--;
			if (!pos[m].d) {
 
				que.push(m);
 
			}
 
		}
 
	}
	if (fur != n) return 0;//fur为排序中的点的个数，如果有点未加入排序中，说明存在环，即不存在拓扑排序
	else return 1;
}
 
 
int main() {
 
	cin >> n >> m;
 
	for (int i = 1; i <= m; i++) {//接收图
 
		int a, b; scanf("%d%d", &a, &b);
 
		pos[a].ne.push_back(b); pos[b].d++;
 
	}
 
	if (bfs()) {
 
		for (int i = 0; i < n; i++)
			cout << p[i] << ' ';
 
	}
	else cout << -1;
 
 
}