拓扑排序

# 拓扑排序 ## 概念 我们知道有一种图叫有向无环图（DAG），这个图有很好的性质，那么如何判断一个图是否是有向无环图呢？答案是对 AOV 网络构造它的 拓扑有序序列（topological order sequence），即将各个顶点排列成一个线性有序的序列，使得 AOV 网络中所有存在的前驱和后继关系都能得到满足。 一般一个工程可以分成若干个子工程，这些子工程称为 活动（activity）。完成了这些活动，整 个工程就完成了。例如，计算机专业课程的学习就是一个工程，每门课程的学习就是整个工程中 的一个活动。  实际上，可以用有向图来表示一个工程。在这种有向图中，用顶点表示活动，用有向边<u, v> 表示活动 u 必须先于活动 v 进行。 这种有向图叫做顶点表示活动的网络（activity on vertices），记 作 AOV 网络。 在 AOV 网络中，如果存在有向边<u, v>，则活动 u 必须在活动 v 之前进行，并称 u 是v 的直 接前驱 直 接前驱（immediate predecessor），v 是 u 的 直接后继（immediate successor）。如果存在有向路径<u, u 1 , u 2 , …, u n , v>，则称 u 是 v 的 前驱（predecessor），v 是 u 的 后继（successor）。 这种前驱与后继的关系有 传递性（transitivity）。例如，如果活动 v 2 是v 1 的后继，v 3 是 v 2 的后 继，那么活动 v 3 也是 v 1 的后继。此外，任何活动不能以它自己作为自己的前驱或后继，这种特性 称为 反自反性（irreflexivity）。 从前驱与后继的传递性和反自反性可以看出，AOV 网络中不能出现有向回路（或称为有向 环）。 不含有向回路的有向图称为 有向无环图（DAG, directed acyclic graph）。 在 AOV 网络中如果出现了有向回路，则意味着某项活动以自己作为先决条件，这是不对的。 如果设计出这样的流程图，工程将无法进行。对于程序而言，将陷入死循环。 因此，对于给定的 AOV 网络，必须先判断它是否是有向无环图。 例如，对 2.25(b)所示的学生选课工程图进行拓扑排序，得到的拓扑有序序列为： C 1 ，C 2 ，C 3 ，C 4 ，C 5 ，C 6 ，C 8 ，C 9 ，C 7 或：C 1 ，C 8 ，C 9 ，C 2 ，C 5 ，C 3 ，C 4 ，C 7 ，C 6 。 学生必须按照拓扑有序的顺序选修课程，才能保证学习任何一门课程时其先修课程都已经学 过。从该例子可以看出，一个 AOV 网络的拓扑有序序列可能不唯一。 ## 拓扑排序的实现 BFS 我们用链式前向星存图，记录每个节点的入度，每次选出入度为0的点放入队列中，每次出队一个点，将这个点能到达的所有点的入度减1，如果哪个能到达的点入度变为0，入队。如果在过程中哪一刻没有入度为0的点，则说明此图不是一个DAG。 [POJ2367](http://poj.org/problem?id=2367) ```cpp #include<cstdio> #include<iostream> #include<queue> using namespace std; const int N=101; queue<int>q; int n,head[N],cnt,in[N],fail,ans[N]; struct tu{ int to,ne; }e[N*N]; inline void add(int u,int v){ cnt++; e[cnt].to=v; e[cnt].ne=head[u]; head[u]=cnt; } void topsort(){ for(int i = 1;i<=n;i++){ if(!in[i]) q.push(i); } while(!q.empty()){ int i = q.front(); q.pop(); ans[++fail]=i; for(int j = head[i];j;j=e[j].ne){ int v = e[j].to; in[v]--; if(!in[v]) q.push(v); } } } int main(){ scanf("%d",&n); for(int i = 1;i<=n;i++){ int x; while(scanf("%d",&x) && x){ add(i,x); in[x]++; } } topsort(); for(int i = 1;i<=n;i++) printf("%d ",ans[i]); return 0; } ```