AOV网及拓扑排序
前天在网上看了一篇博客，觉得写的很不错，小编转载一下，顺便加了点自己的理解。
一、AOV网
有向无环图（Directed Acycline Graph, DAG）是一类特殊的有向图。DAG有着广泛应用，AOE网和AOV网都是DAG的典型应用。那什么是AOV网呢？
在有向图中，用顶点表示活动，用有向边表示活动i 是活动j的必须条件。这种有向图称为用顶点表示活动的网络(Active on vertices)，简称AOV网络。 AOV网的边不设权值，若存在边<Vi,Vj>则表示活动i必须发生在活动j之前。
在AOV网络中，如果活动Vi必须在Vj之前进行，则存在有向边<Vi,Vj>，并称Vi是Vj的直接前驱，Vj是Vi的直接后继。
举个例子：
image
上图，课程代表活动，学习一门课程就表示进行一项活动，学习每门课程的先决条件是学完它的全部先修课程。比如学数据结构必须先学习C语言和离散数学，学习《计算机导论》课程则可以随时安排，因为它是基础课程，没有先修课。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。
举个例子:
image
由边可得B活动必须在A活动之后，由<B,C>边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由<C,A>边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是必须避免的。
二、拓扑排序
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
实际上，对一个有向无环图（Directed Acyclic Graph简称DAG）G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
image
上图是一个学习java的表格。从图中可以看到，学习java系类(部分)从java基础，到jsp/servlet，到ssm，到springboot，springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础和html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么，这个学习过程即构成一个拓扑序列。当然这个序列也不唯一，你可以对不关联的学科随意选择顺序（比如html和java可以随便先开始哪一个）。
那上述序列可以简单表示为：
image
其中五种均为可以选择的学习方案，对课程安排可以有参考作用，当然，五个都是拓扑序列。只是选择的策略不同！
一些其他注意：
DGA：有向无环图
AOV网：数据在顶点 可以理解为面向对象
AOE网：数据在边上，可以理解为面向过程！
而我们通俗一点的说法，就是按照某种规则将这个图的顶点取出来，这些顶点能够表示什么或者有什么联系。
规则：
1、图中每个顶点只出现一次。
2、A在B前面，则不存在B在A前面的路径。(不能成环！！！！)
3、顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一。
三、算法实例分析
image
正常步骤为(方法不一定唯一)：
1、从DGA图中找到一个没有前驱的顶点输出。(可以遍历，也可以用优先队列维护)
2、删除以这个点为起点的边。(它的指向的边删除，为了找到下个没有前驱的顶点)
3、重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！
对于上图的简单序列，可以简单描述步骤为：
1：删除1或2输出
image
2：删除2或3以及对应边
image
3：删除3或者4以及对应边
image
4：重复以上规则步骤
image
这样就完成一次拓扑排序，得到一个拓扑序列，但是这个序列并不唯一！从过程中也看到有很多选择方案，具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。
四、算法分析
对于拓扑排序，如何用代码实现呢？对于拓扑排序，虽然在上面详细介绍了思路和流程，也很通俗易懂。但是实际上代码的实现还是很需要斟酌的，如何在空间和时间上能够得到较好的平衡且取得较好的效率？
首先要考虑存储。对于节点，首先他有联通点这么多属性。遇到稀疏矩阵还是用邻接表比较好。因为一个节点的指向节点较少，用邻接矩阵较浪费资源。
我们具体的代码思想为：
1：新建node类，包含节点数值和它的指向(这里直接用list集合替代链表了)
2：一个数组包含node(这里默认编号较集中)。初始化，添加每个节点指向的时候同时被指的节点入度+1！(A—>C)那么C的入度+1；
3：扫描一遍所有node。将所有入度为0的点加入一个栈(队列)。
4：当栈(队列)不空的时候，抛出其中任意一个node(栈就是尾，队就是头，顺序无所谓，上面分析了只要同时入度为零可以随便选择顺序)。将node输出，并且node指向的所有元素入度减一。如果某个点的入度被减为0，那么就将它加入栈(队列)。
5：重复上述操作，直到栈为空。
这里主要是利用栈或者队列储存入度只为0的节点，只需要初次扫描表将入度为0的放入栈(队列)中。
这里你或许会问为什么。
因为节点之间是有相关性的，一个节点若想入度为零，那么它的父节点(指向节点)肯定在它为0前入度为0，拆除关联箭头。从父节点角度，它的这次拆除联系，可能导致被指向的入读为0，也可能不为0(还有其他节点指向儿子)。
小编用的邻接矩阵创建矩阵，使用栈辅助存储数据，邻接表也是相同的算法。
template <class T, class E>
bool GraphMatrix<T, E>::TopologicalSort ()
{
//有向网G采用邻接矩阵存储结构，求各顶点事件的最早发生时间ve，
//ToPoStack为拓扑序列顶点栈，IndegreeZeroStack为零入度顶点栈。
//若G无回路，则用栈返回G的一个拓扑序列，且函数返回True,否则返回False
int count=0; //计数器对输出顶点记数
int ch;
FindInAndOutDegree(); //求出图中各顶点的入度
Initial (IndegreeZeroStack); //堆栈初始化，存放入度为零的顶点
Initial (ToPoStack);
for (int i=0; i<numVertices; i++){
if (indegree[i]==0) {
Push (IndegreeZeroStack,i); //入度为零的顶点入栈
}
}
//cout<<S.Stackcount<<endl;
for (int i=0; i<numVertices; i++ ){
earlist[i]=0; //ve初始化
}
while (!StackEmpty (IndegreeZeroStack))
{
Pop (IndegreeZeroStack,ch); //顶点出S栈并入T栈，count记数
int i=ch;
Push (ToPoStack,ch);
count++;
// int i=getVertexPos(ch);//顶点ch对应的位置i号
for(int j=0;j<numVertices; j++){
if(i!=j && getWeight(i,j)<maxWeight){
if (!( --indegree[j] ))
Push (IndegreeZeroStack,j); //若入度为零，入栈
if (( earlist[i]+getWeight(i,j)) >earlist[j] )
earlist[j] =earlist[i]+getWeight(i,j);
//修改k号顶点的最早发生时间
//ve的求法：ve(j)=Max{ve(i)+dut(<i,j>)} <i,j>∈S,j=1,2,…,n-1
}
}
}
cout<<"到达各个状态的最早时间："<<endl;
for(int i=0;i<numVertices;i++)
{
cout<<getValue(i)<<":"<<earlist[i]<<endl;
}
if (count<(numVertices-1)){
cout<<"回路"<<endl;
return false; //如输出顶点数少于图中顶点数，则该图有回路
}
else {
return true;
}
}
