dfs与bfs的很直接的应用就是拓扑排序。
拓扑排序如果用数组来模拟链表进行操作，既解决了稀疏图的空间问题，又解决了用链表进行操作麻烦的问题
但是拓扑排序并不是数字大小之间的排序，而是某些事情之间的顺序有着相互的顺序关系，就好比说你学了c语言基础以后再继续学习更高深的数据结构学完数据结构之后才能够去做一些比较难一些的算法题
第一个题 hdu3342 （基于bfs的拓扑排序）
HDU3342
给出一部分人的师徒关系，让我们来判断是否合法，比如说（1是2的师傅，2是1的师傅关系不合法）也就是可以理解为形成了自环，可以拓扑排序的要求是这个图是有向无环图，如果拓扑排序没有矛盾，也就是说所有结点都被遍历过，此时可以输出yes，可以用一个变量来记录一下是否全部遍历过，如果变量等于人数则输出yes
代码
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod;
using namespace std;
int n,m;
vector < vector<int> > imap;
int pre[1000];
bool topsort(){
queue <int> q;
for(int i=0;i<m;i++){
if(pre[i]==0)
q.push(i);
}
int ans=0;
while(!q.empty()){
int temp=q.front();
q.pop();
ans++;
for(int i=0;i<(int)imap[temp].size();i++){
int x=imap[temp][i];
pre[x]--;
if(pre[x]==0){
// cout<<x<<" ";
q.push(x);
}
}
}
//cout<<ans<<endl;
return ans==m;
}
int main()
{
while(cin>>m>>n){
if(m==0&&n==0) break;
int x,y;
imap.clear();
imap.resize(m+1);
memset(pre,0,sizeof(pre));
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
imap[x].push_back(y);
pre[y]++; //这个是用来记录与他相邻的点并且在他前面的点的个数
}
// for(int i=0;i<m;i++) cout<<pre[i]<<" ";
if(topsort()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
第二题 poj1270 （基于bfs的拓扑排序） （按字典序输出-正向建图）
poj1270
这个题可能没有前面那个题容易，但是个人感觉蛮重要的，。
注意的几点：
（1）输入的字符之间有空格
（2）每组输出之间有一个空行
他既然要按字典序输出，我们可以提前将他排好序，然后挨个检验是否符合标准，字符x前面不能有字符y，就可以转化为拓扑排序来做，（也就是说当某个字母是入度为0的字母，我们就可以将他放进去，如果入度不为零，说明这个字符前面还有别的字符，如果我们放进去，输出的字符肯定会不合法）
//#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
//const double pi = acos(-1);
typedef long long ll;
ll mod;
using namespace std;
int n,m,f;
int pre[1000];
int mp[300][300];
char put[100];
string s;
char s1[300];
int s2[300];
int x,y;
void toposort(int steps){
if(steps==f){
printf("%s\n",put);
return ;
}
for(int i=0;i<f;i++){
if(pre[i]==0){
// cout<<i<<endl;
pre[i]--;
for(int j=0;j<f;j++)
if(mp[i][j]==1) pre[j]--;
put[steps]=s1[i];
toposort(steps+1);
pre[i]++; //回溯的思想
for(int j=0;j<f;j++)
if(mp[i][j]==1) pre[j]++;
}
}
return ;
}
int main()
{
//freopen("out.txt","w",stdout);
while(getline(cin,s)){
f=0;
memset(mp,0,sizeof(mp));
memset(pre,0,sizeof(pre));
memset(s2,0,sizeof(s2));
memset(s1,0,sizeof(s1));
memset(put,0,sizeof(put));
for(int i=0;i<s.size();i++){
if(isalpha(s[i])){
s1[f++]=s[i];
}
}
sort(s1,s1+f);
getline(cin,s);
for(int i=0;i<f;i++){
s2[s1[i]]=i;
}
bool flag=true;
for(int i=0;i<s.size();i++){
if(isalpha(s[i])){
if(flag){
flag=false;
x=s[i];
}
else{
flag=true;
y=s[i];
mp[s2[x]][s2[y]]=1;
pre[s2[y]]++;
}
}
}
toposort(0);
printf("\n");
}
return 0;
}
第三题HDU4857（基于bfs的拓扑排序）按编号排序-反向建图
HDU4857
这个题跟之前的的按照字典序输出有一定的区别
意思是说编号小的尽量在这一串的前面
我们直接用优先队列进行储存，让最大的数先出列，最后逆序输出就可以。
这个时候你可能会问为什么不直接优先队列从小到大排序，正序输出呢，其实我也不知道为什么
你可以举个例子比如说这个排序走的路径如果按照从小到大他输出的路径是1->4->5->3->2，但是正确的是1->5->3->4->2，因为第二个3更靠前。
//#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <stdlib.h>
#define maxn 1000005
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
//const double pi = acos(-1);
typedef long long ll;
ll mod;
using namespace std;
vector < vector<int> > vec;
vector <int> put;
int n,m;
int pre[30010];
void toposort(){
priority_queue<int,vector<int>,less<int> > q;
for(int i=1;i<=n;i++){
if(pre[i]==0){
q.push(i);
}
}
while(!q.empty()){
int temp=q.top();
q.pop();
put.push_back(temp);
for(int i=0;i<vec[temp].size();i++){
int x=vec[temp][i];
pre[x]--;
if(pre[x]==0) q.push(x);
}
}
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n>>m;
vec.clear();
put.clear();
vec.resize(n+1);
memset(pre,0,sizeof(pre));
for(int i=0;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
vec[y].push_back(x);
pre[x]++;
}
toposort();
for(int i=put.size()-1;i>=0;i--){
if(i==0) printf("%d\n",put[i]);
else printf("%d ",put[i]);
}
}
return 0;
}
京公网安备 11010502036488号