本文主要是介绍DFS拓扑排序(算法导论思路)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;const int maxn = 10005;
int color[maxn]; //0代表白色,1代表灰色,2代表黑色
vector<int> vec[maxn]; //邻接表
int step; //全局变量代表总步数
int stime[maxn]; //每个点遍历的时候的起始时间
int etime[maxn]; //每个点遍历的时候的终止时间
bool exist[maxn]; //判断图中是否存在该点
int parent[maxn];
vector<int> order; //按完成实现先后排序后插入,完成拓扑排序.
int cnt; //统计总的点数
int result[maxn];
map<int,int> Map; //结点编号和结束时间的键值对，因为排序会乱 void init()
{memset(color,0,sizeof(color)); //初始化都为白色memset(stime,0,sizeof(stime));memset(etime,0,sizeof(etime));memset(parent,-1,sizeof(parent)); //初始化每个结点的父亲都为-1 memset(result,-1,sizeof(result));step = 0;cnt = 0;
}void dfs_visit(int u)
{int i;int pos;step++;stime[u] = step;color[u] = 1; //刚刚访问到这一结点，置为灰色 int len = vec[u].size();for(i=0;i<len;i++){pos = vec[u][i];if(color[pos] == 0){parent[pos] = u;dfs_visit(pos);}}color[u] = 2; //邻接点全部遍历完了，置为黑色 step++;etime[u] = step;
}void dfs()
{int i;for(i=1;i<maxn;i++){if(exist[i] != false){cnt++;}if(exist[i] != false && color[i] == 0) //存在这个点且这个点为白色 {dfs_visit(i);}}
}void print()
{int i;for(i=0;i<maxn;i++){if(exist[i] != false){cout<<i<<"点的信息如下:"<<endl;cout<<"起始时间:"<<" "<<stime[i]<<" "<<"结束时间:"<<" "<<etime[i]<<endl; }}
}void topo_order()
{int i;cout<<"拓扑排序结果为(点):"<<endl;for(i=maxn;i>=1;i--){if(etime[i] != 0){if(i != 1){cout<<Map[etime[i]]<<"->";}else{cout<<Map[etime[i]];}}}cout<<endl;cout<<"拓扑排序结果为(时间):"<<endl; for(i=1;i<=maxn;i++){if(etime[i] != 0){if(i != cnt)cout<<etime[i]<<"->";elsecout<<etime[i];}else{break;}}cout<<endl;
}int main()
{int start;int num1,num2;cnt = 0;init();freopen("1.txt","r",stdin);while(cin>>num1>>num2 && num1 != 0 && num2 != 0){vec[num1].push_back(num2); //有向图 exist[num1] = true;exist[num2] = true;}/*for(int i=0;i<maxn;i++){if(exist[i] == true){cout<<i<<endl;}}*/int i;dfs();for(i=1;i<maxn;i++){if(etime[i] != 0){Map[etime[i]] = i;//cout<<etime[i]<<" "<<i<<endl;}}//print();sort(etime+1,etime+cnt+1);/*for(int i=1;i<=cnt;i++){cout<<etime[i]<<endl;}*/topo_order();return 0;
} 这篇关于DFS拓扑排序(算法导论思路)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
