链接:https://vjudge.net/problem/Aizu-GRL_4_B
下面基于bfs和dfs分别进行实现
bfs:
思路:通过寻找入度为0的点作为拓扑排序的起点,对其相邻点进行搜索并减少对应入度,搜索完成后将该点加入排序队列,并在图中删除该点,对后面的点进行继续搜索.
代码:
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAX = 1000000;
const int INF = (1<<29);
int n;
vector<int> G[MAX];
vector<int> result;
queue<int> line;
int indeg[MAX];
bool V[MAX];
void bfs(int s){
line.push(s);
V[s] = true;
while(!line.empty()){
int u = line.front();
line.pop();
result.push_back(u);
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
indeg[v]--;
if(indeg[v]==0&&V[v]==false){
V[v] = true;
line.push(v);
}
}
}
}
void tsort(){
for(int i=0;i<n;i++){
for(int u=0;u<G[i].size();u++){
int v = G[i][u];
indeg[v]++;
}
}
for(int i=0;i<n;i++){
if(indeg[i]==0&&V[i]==false) bfs(i);
}
for(int u = 0;u<result.size();u++)
cout<<result[u]<<endl;
}
int main(){
memset(indeg,0,sizeof(indeg));
memset(V,0,sizeof(V));
int num,a,b;
cin>>n>>num;
while(num--){
cin>>a>>b;
G[a].push_back(b);
}
tsort();
return 0;
}
dfs:
思路:若图中u,v间存在路径,则v在排序中一定在u之后,dfs搜索只需保证每一条路径的v都在u之后即可得出最后的排序结果，此时并不需要回溯。
代码：
#include<iostream>
#include<vector>
#include<list>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 1000000;
int n;
vector<int> G[MAX];
list<int> result;
bool V[MAX];
void dfs(int s){
V[s] = true;
for(int i=0;i<G[s].size();i++){
int v = G[s][i];
if(V[v]==false)dfs(v);
}
result.push_front(s);
}
int main(){
memset(V,0,sizeof(V));
int num,a,b;
cin>>n>>num;
while(num--){
cin>>a>>b;
G[a].push_back(b);
}
for(int i=0;i<n;i++){
if(V[i]==false) dfs(i);
}
for(list<int>::iterator it = result.begin();it!=result.end();it++)
cout<<*it<<endl;
return 0;
}
注意：因为一张图可能存在多个排序结果，所以同一图用bfs和dfs可能得出不同的结果。
