拓扑排序
对一个有向图构造拓扑序列的过程称为拓扑排序（不唯一）
思想
- 从AOV网选择一个没有前驱的顶点并输出
- 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧
- 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点
设计数据结构
1、图的存储结构：采用邻接表存储，在顶点增加一个入度域
2、栈S存储所有无前驱的顶点
伪代码描述
1.栈S初始化；累加器count初始化；
2.扫描顶点表，将没有前驱（入度为0）的顶点压栈；
3.当栈S非空时循环
3.1 j=栈顶元素出栈；输出顶点j；count++；
3.2 对顶点j的每一个邻接点k执行：
3.2.1 将顶点k的入度减1；
3.2.2 如果顶点k入度为0，则将顶点k入栈；
4.if（count<G.vertexNum）输出有回路信息；
算法实现
void TopSort(ALGraph G)
{
S.top=0; //顺序栈S并初始化
count=0; //累加器count初始化
for(i=0;i<G.vertexNum;i++) //扫描顶点表
{
if(G.adjlist[i].in==0)
{
S.base[++S.top]=i; //将入度为0的顶点压栈
}
}
while(S.top!=0) //栈不为空，即还有入度为0的顶点时
{
j=S.base[S.top--]; //从栈中取出一个入度为0的顶点
cout<<G.adjlist[j].vertex;
count++;
p=G.adjlist[j].firstedge; //工作指针p初始化
while(p!=NULL) //扫描顶点表，找出顶点j的所有边
{
k=p->adjvex;
G.adjlist[k].in--; //将入度减1
if(G.adjlist[k].in==0) //如果为0，则将该顶点入栈
{
S.base[++S.top]=k;
}
p=p->nextarc;
}
}
if(count<vertexNum)
cout<<"有回路";
}