一.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;
}
}
}
