了解AOV网

某些子节点必须在其他的一些子节点前处理，先后关系为有向边，这样的有向图为顶点表示活动的网，我们称为AOV网(Activity On Vertex Network)。在AOV网中，若从顶点i到顶点j之间存在一条有向路径，称顶点i是顶点j的前驱，或者称顶点j是顶点i的后继。 AO网必定是有向无环图，否则会自我矛盾。 矛盾证明： 如下图，经过观察，可得到1的前驱是1，即要先处理1，必须先处理1，这显然是有病的。

拓扑排序

拓扑排序只适用于AOV网 在AOV网中所有结点可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。 如上图，拓扑序列可以为A–>B–>E–>G–>D–>C–>F

排序方法

（先用邻接表存储好了的）

一、栈或队列

思路：

构造一个队列Q或栈S把所有没有入度为0的节点放入Q或S；当Q或S还有结点的时候，执行下面步骤： 3.1 从Q或S中取出一个顶点n(将n从Q中删掉)，并输出； 3.2 对n每一个邻接点m(n是起点，m是终点)； 3.2.1 去掉边<n,m>; 3.2.2 如果点m的入度为0，则把m放入Q或S;

代码实现如下： 栈：

while(!s.empty()) { int temp=s.top(); int t=head[temp]; cout<<temp<<" "; s.pop(); while(t) { h[e[t].v]--;//去掉节点后，终点的入度减少 if(!h[e[t].v]) s.push(e[t].v);//如果入度为0，入栈 t=e[t].next;//刷新去找上一个边 } }

队列：

while(!q.empty()) { int temp=q.front(); int t=head[temp]; cout<<temp<<" "; q.pop(); while(t) { h[e[t].v]--;//去掉节点后，终点的入度减少 if(!h[e[t].v]) q.push(e[t].v);//如果入度为0，入队 t=e[t].next;//刷新去找上一个边 } }

二、最大（最小）拓扑序

注：最小拓扑序也是字典序 使用优先队列进行替换即可，这里上字典序代码

priority_queue<int,vector<int>,greater<int> > q;//如果是最大，把greater改为less void topsort() { for(int i=1;i<=n;i++) if(!h[i]) q.push(i);//遍历一遍找起始点 while(!q.empty()) { int temp=q.top(); int t=head[temp]; cout<<temp<<" "; q.pop(); while(t) { h[e[t].v]--;//去掉节点后，终点的入度减少 if(!h[e[t].v]) q.push(e[t].v);//如果入度为0，入队 t=e[t].next;//刷新去找上一个边 } } }