如果一个有向图中没有包含简单的回路，这样的图为有向无环图。

图中的顶点代表事件（活动），图中的有向边说明了事件之间的先后关系。这种用顶点表示活动，用弧表示活动时间的优先关系的有向图称为顶点表示活动的网，简称AOV网（Active On Vertex Network）。

在AOV网中，若顶点u与顶点v之间存在一条有向边<u,v>，则说明事件u必须先于事件v完成。此处将u称为v的直接前驱，v称为u的直接后继。

对AOV网进行拓扑排序的方法和步骤如下：

（1）在有向图中找一个没有前驱（入度为0）的顶点并输出。

（2）在图中删除该顶点以及所有与该顶点出发的有向边。

（3）反复执行步骤（1）和步骤（2），直到所有顶点均被输出，或者AOV网中再也没有入度为0的顶点存在为止。

算法的两种结束情况：

（1）所有顶点全部输出，表明对该图的拓扑排序成功。

（2）图中有部分结点没有输出，但已经不存在入度为0的顶点，说明此AOV网中存在环。

 

直接输入（真的好麻烦，输错一个就要重来）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>const int M = 20;typedef struct node
{int adjvex;struct node *next;
}edgenode;typedef struct de //带顶点入度的头节点定义
{edgenode *FirstEdge;char vertex;int id;//顶点的入度
}vertexnode;typedef struct //AOV网的邻接表结构
{vertexnode adjlist[M];int n,e;
}AovGraph;//创建AOV网络的邻接表
void creat(AovGraph *g)
{int i,j,k;edgenode *s;printf("请输入点数和边数：");scanf("%d%d",&g->n,&g->e);getchar();printf("\n请输入顶点序号以及该顶点入度：\n");for(i=0;i<g->n;i++){scanf("%c",&g->adjlist[i].vertex);scanf("%d",&g->adjlist[i].id);getchar();g->adjlist[i].FirstEdge=NULL;}printf("\n请输入有向边：\n");for(k=0;k<g->e;k++){scanf("%d%d",&i,&j);s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=g->adjlist[i].FirstEdge;g->adjlist[i].FirstEdge=s;}
}//打印AOV网络的邻接表
void print(AovGraph g)
{int i,j,k;edgenode *p;for(i=0;i<g.n;i++){printf("入度：%d 地址：%d char值：C%c->  ",g.adjlist[i].id,i,g.adjlist[i].vertex);p=g.adjlist[i].FirstEdge;if(p == NULL){printf("NULL\n");continue;}while(p){printf("%d",p->adjvex);if(p->next){printf(" -> ");}p=p->next;}printf("\n");}return ;
}//拓扑排序算法
int TopSort(AovGraph g)
{int k=0,i,j,v,flag[M];int queue[M];int front ,rear;edgenode *p;front = 0;rear = 0;memset(flag,0,sizeof(flag));//访问标记初始化for(i=0;i<g.n;i++){if(g.adjlist[i].id==0 && flag[i]==0){queue[rear++]=i;flag[i]=1;}}printf("\nAOV网的拓扑排序为：\n");while(front < rear)//当队列空间不为空时{v = queue[front++];//队首元素出队printf("%c ",g.adjlist[v].vertex);k++;//计数器加一p=g.adjlist[v].FirstEdge;while(p)//将所有与v邻接的顶点的入度减一{j=p->adjvex;if(--g.adjlist[j].id==0 && flag[j]==0){queue[rear++]=j;flag[j]=1;}p=p->next;}}return k;
}int main ()
{int node_num;AovGraph g;creat(&g);print(g);node_num=TopSort(g);printf("\n一共输出%d个结点\n",node_num);if(g.n==node_num)printf("所有顶点全部输出，对该图拓扑排序成功！\n");elseprintf("此AOV网中存在着环，无法完成拓扑排序!\n");return 0;
}

  

 

使用文件读取数据（十分方便）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>const int M = 20;typedef struct node
{int adjvex;struct node *next;
}edgenode;typedef struct de //带顶点入度的头节点定义
{edgenode *FirstEdge;char vertex;int id;//顶点的入度
}vertexnode;typedef struct //AOV网的邻接表结构
{vertexnode adjlist[M];int n,e;
}AovGraph;//创建AOV网络的邻接表
void creat(AovGraph *g)
{int i,j,k;edgenode *s;FILE *f;f=fopen("test.txt","r");if(f){fscanf(f,"%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){fscanf(f,"%1s %d",&g->adjlist[i].vertex,&g->adjlist[i].id);g->adjlist[i].FirstEdge=NULL;}for(k=0;k<g->e;k++){fscanf(f,"%d%d",&i,&j);s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=g->adjlist[i].FirstEdge;g->adjlist[i].FirstEdge=s;}fclose(f);}else{g->n=0;}
}//打印AOV网络的邻接表
void print(AovGraph g)
{int i,j,k;edgenode *p;for(i=0;i<g.n;i++){printf("入度：%d 地址：%d char值：C%c->  ",g.adjlist[i].id,i,g.adjlist[i].vertex);p=g.adjlist[i].FirstEdge;if(p == NULL){printf("NULL\n");continue;}while(p){printf("%d",p->adjvex);if(p->next){printf(" -> ");}p=p->next;}printf("\n");}return ;
}//拓扑排序算法
int TopSort(AovGraph g)
{int k=0,i,j,v,flag[M];int queue[M];int front ,rear;edgenode *p;front = 0;rear = 0;memset(flag,0,sizeof(flag));//访问标记初始化for(i=0;i<g.n;i++){if(g.adjlist[i].id==0 && flag[i]==0){queue[rear++]=i;flag[i]=1;}}printf("\nAOV网的拓扑排序为：\n");while(front < rear)//当队列空间不为空时{v = queue[front++];//队首元素出队printf("%c ",g.adjlist[v].vertex);k++;//计数器加一p=g.adjlist[v].FirstEdge;while(p)//将所有与v邻接的顶点的入度减一{j=p->adjvex;if(--g.adjlist[j].id==0 && flag[j]==0){queue[rear++]=j;flag[j]=1;}p=p->next;}}return k;
}int main ()
{int node_num;AovGraph g;creat(&g);print(g);node_num=TopSort(g);printf("\n一共输出%d个结点\n",node_num);if(g.n==node_num)printf("所有顶点全部输出，对该图拓扑排序成功！\n");elseprintf("此AOV网中存在着环，无法完成拓扑排序!\n");return 0;
}