一.AOV网的概念（Activity On Vertex Network）

        在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系。这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）。

AOV网的特点：

（1）AOV网中的弧表示活动之间存在的某种制约关系。

（2）AOV网中不能出现回路。

二.拓扑排序的定义

拓扑序列：

设G=（V，E）是一个具有n个顶点的有向图，V中的顶点序列称为一个拓扑序列，当且仅当满足下列条件：若从顶点到有一条路径，则在顶点序列中顶点必在之前。

拓扑排序：

对一个有向图构造拓扑序列的过程

拓扑排序是对给定的AOV网判断网中是否存在环的一种算法，若网中所有顶点都在它的拓扑有序序列中，则该AOV网中必定不存在环。

三.拓扑排序的基本思想

（1）从AOV网中选择一个没有前驱的顶点并且输出；

（2）从AOV网中删除该顶点，并且删去所有以该顶点为头的的弧；

（3）重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。

四.拓扑排序实现需要的数据结构

1.图的存储结构：

邻接表存储，在顶点表中增加一个入度域in

2.栈S：

存储所有无前驱的顶点

五.拓扑排序的伪代码

1.栈S初始化，累加器count初始化；

2.扫描顶点表，将没有前驱的顶点压栈；

3.当栈非空时循环：

        3.1  保存弹栈元素，输出 ，累加器加一；

        3.2 将顶点 的各个邻接点的入度减一；

        3.3 将新的入度为0的顶点入栈；

4.如果count<vertexNum，则图中有回路

六.代码实现

#include <iostream>
#include <stack>
#include <string.h>
using namespace std;

struct node{
    int number;
    struct node *next;
};

struct vertex{
    int in;//入度
    char vertex;
    struct node *firstedge;
};

class ALGraph{
private:
    int vertexNum,arcNum;
    struct vertex *v;
public:
    ALGraph(int n,int e);
    ~ALGraph();
    void topology();
    void display();
};

int main(int argc, const char * argv[]) {
    ALGraph G(7, 10);
    //G.display();
    G.topology();
    return 0;
}

ALGraph::ALGraph(int n,int e){
    int p,q;
    struct node *s;
    vertexNum=n;
    arcNum=e;
    v=new struct vertex[n];
    
    for(int i=0;i<n;i++){
        v[i].firstedge=NULL;
        v[i].in=0;
        v[i].vertex=i+'a';
    }
    
    for(int i=0;i<e;i++){
        
        cin>>p>>q;
        s=new struct node;
        s->number=q;
        s->next=v[p].firstedge;
        v[p].firstedge=s;
        v[q].in++;
    }
    
}
ALGraph::~ALGraph(){
    struct node *p,*q;
    for(int i=0;i<vertexNum;i++){
        p=v[i].firstedge;
        while(p){
            q=p->next;
            delete p;
            p=q;
        }
        v[i].firstedge=NULL;
    }
    delete [] v;
}

void ALGraph::topology(){
    stack <struct vertex> s;
    int count=0,i,j;
    struct vertex vj;
    
    for(i=0;i<vertexNum;i++){
        if(v[i].in==0){
            s.push(v[i]);
        }
    }
    while(!s.empty()){
        vj=s.top();
        s.pop();
        cout<<vj.vertex<<endl;
        count++;
        struct node *p=vj.firstedge;
        while(p){
            j=p->number;
            v[j].in--;
            if(v[j].in==0){
                s.push(v[j]);
            }
            p=p->next;
        }
    }
    if(count!=vertexNum){
        cout<<"该图中有回路！！！"<<endl;
    }
}

void ALGraph::display(){
    struct node *p;
    int i;
    for(int i=0;i<vertexNum;i++){
        p=v[i].firstedge;
        while(p){
            cout<<v[i].vertex<<"->";
            char c=p->number+'a';
            cout<<c<<endl;
            p=p->next;
        }
        
    }
}