拓扑排序

了解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

排序方法

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

一、栈或队列

思路：

1. 构造一个队列Q或栈S
2. 把所有没有入度为0的节点放入Q或S；
3. 当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;//刷新去找上一个边 
		}
	}
}