首页 > 代码库 > 拓扑排序
拓扑排序
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
拓扑排序可以通过DFS来实现。在排序某一个节点时，首先等到它的所有儿子节点排序完成后，再排序它本身。拓扑排序基于这样一个事实：若u到v存在通路，则u一定排在v的前面。如果图有环，则将不可能排出拓扑序列。
/*UVa10305 - Ordering Tasks---DFS进行拓扑排序--*/#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<string.h>#include<vector>#include<algorithm>using namespace std;const int maxn = 100 + 5;vector<int>vec[maxn]; //邻接表int vis[maxn];int topo[maxn];int t;//默认顶点从0...n-1编号bool dfs(int u){ vis[u] = -1; //等待排序 for (int i = 0; i < (int)vec[u].size(); i++){ int v = vec[u][i]; if (vis[v] < 0)return false; //存在环,排序失败 else if (!vis[v] && !dfs(v))return false; //它的子节点排序失败 } vis[u] =1; //标志当前节点排序完成 topo[--t] = u; //加入排序列表中 return true;}bool toposort(int n){ t = n; memset(vis, 0, sizeof(vis)); //初始态为未排序 for (int i = 0; i < n; i++)if (!vis[i]) if (!dfs(i))return false; return true;}int main(){ int m, n,u,v; while (scanf("%d%d",&n, &m)&&n){ for (int i = 0; i < n; i++)vec[i].clear(); for (int i = 0; i < m; i++){ scanf("%d%d", &u, &v); u--; v--; vec[u].push_back(v); } toposort(n); printf("%d", topo[0]+1); for (int i = 1; i < n; i++) printf(" %d", topo[i]+1); printf("\n"); } return 0;}
拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。