数据结构

了解拓补排序前，我们先回顾离散数学中关于偏序和全序的定义： 若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序(Partial Order)，如果对每个x，yEX必有xRy或yRx，则称R是集合X上的全序关系。 · 直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。

那么什么是拓扑排序(Topological Sort)?我们说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

我们知道，用顶点表示活动，用弧表示活动间的优先关系的有向图称作顶点表示活动的网，英文即Activity On Vertex Network ，简称AOV-网。 在这个网中，从顶点i到顶点j有一条有向路径，则i是j的前驱；j是i的后继。若是网中的一条弧，那么i是j的直接前驱；j是i的直接后继。 可参考（b）来理解这句话。

（a）表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v₂≤v₃。的弧（符号“≤”表示v₂领先于v₃)，则(a)表示的亦为全序，且这个全序称为拓扑有序(Topological Order)，而由偏序定义得到拓扑有序的操作便是拓扑排序。

AOV-网特点: 1.AOV-网中的弧表示活动之间存在的某种制约关系。 2.AOV-网中不能出现回路。

对程序的数据流图来说，首先要判定所给定的AOV-网中是否存在环。检测方法就是对有向图构造其顶点的拓补有序序列，若网中所有的顶点都在他的拓扑有序序列中，则该AOV-网中必定不存在环，那么这样设计出来的流程图，工程可以正常进行。

先看简单的：

基本思想： （1）从AOV网中选择一个没有前驱的顶点并且输出; （2）从AOV网中删去该顶点，并且删去所有以该顶点)为尾的弧; （3）重复上述两步，直到全部顶点都被输出，或AOV-网中不存在没有前驱的顶点。 ·拓扑排序后，有向图有如下两个拓扑有序序列：

拓扑序列：C1 , C2 , C3 , C4 , C5 , C6 拓扑序列：C1 , C2 , C3 , C4 , C5 , C6 ,C7

设计数据结构： （1）.图的存储（利用邻接表存储，在顶点表中增加一个入度域in） （2）.栈M（存储所有无前驱的顶点。也可以用队列。） 步骤：扫描顶点表，将堆栈初始化。将入度为0的顶点B,E压入堆栈。 弹出堆栈，取出栈顶元素E;根据顶点E的firstEdge遍历所有的边，将其所指向的各个顶点的入度值-1。 在处理时，如果发现某个顶点的入度值为0，则压入堆栈。

核心代码：

拓扑排序算法—伪代码

1.栈M初始化;累加器count初始化; 2.扫描顶点表，将没有前驱的顶点压栈; 3.当栈M非空时循环 3.1 Vj=退出栈顶元素;输出Vj;累加器加1; 3.2将顶点Vj的各个邻接点的入度减1; 3.3将新的入度为0的顶点入栈; 4.if (count //in为0则压栈 if(adjList[i].in==0){ s.push(adjList[i]); } } while(!s.empty()){ //循环终止条件：栈为空 vertexNode v=s.top(); //弹栈输出 s.pop(); cout //如果某结点的in变为0，则将其压栈 s.push(adjList[a->adjvex]) ; } a=a->next; } } if(count int in; //in是入度 string vertex; //顶点信息 ArcNode *firstEdge; }vertexNode,VertexNode[MAX]; class ALGraph{ private: int vertexNum,arcNum; //顶点数，边数 VertexNode adjList; //顶点数组 stack s; //栈 int count=0; //计数 public: ALGraph(string v[],int n,int e); void display(); //打印邻接表 void TopologicalSort(); //拓扑排序 }; void ALGraph::TopologicalSort(){ for(int i=0;i s.push(adjList[i]); } } while(!s.empty()){ //循环终止条件：栈为空 vertexNode v=s.top(); //弹栈输出 s.pop(); cout //如果某结点的in变为0，则将其压栈 s.push(adjList[a->adjvex]) ; } a=a->next; } } if(count //顶点初始化 adjList[i].in=0; adjList[i].vertex=v[i]; adjList[i].firstEdge=NULL; } ArcNode *s; int vi,vj; for(int i=0;i 　　 cout int n,e; coute; cout int adjvex; //邻接点域，存储该顶点对应的下标 int weight; //用于存储权值，对于非网图可以不需要 struct EdgeNode* next; //下一个结点 }; struct VertexNode{ int in; //入度 VerType data; //值 struct EdgeNode* firstedge; //邻接表头指针 }; struct Graph{ struct VertexNode vers[MAXVEX]; int vernum, arcnum; //顶点数和边数 }; /* 拓扑排序，若G没有回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */ int TopologicalSort(struct Graph* G){ struct EdgeNode* e; int i, k, gettop; int top = 0; //栈指针下标 int count = 0; //统计输出顶点个数 int* stack; //存储入度为0的顶点 stack = (int*)malloc(G->vernum * sizeof(int)); for(i = 0;ivernum;i++) //遍历所有结点 if(G->vers[i].in == 0) stack[++top] = i; //将入度为0的顶点入栈 while(top != 0){ gettop = stack[top--]; //出栈 printf("%c ",G->vers[gettop].data); count++; //统计输出顶点数 for(e=G->vers[gettop].firstedge; e; e = e->next){ //弧表遍历 k = e->adjvex; if(!(--G->vers[k].in)) //将k号顶点邻接点的入度减1 stack[++top] = k; //若为0则入栈，以便下次循环输出 } } if(count vernum) //如果count小于顶点数，说明存在环 return 0; else return 1; } /* 图初始化 */ void CreateGraph(struct Graph* G){ int i, m, n; printf("输入顶点数和边数：\n"); scanf("%d %d",&G->vernum, &G->arcnum); printf("输入顶点值：\n"); getchar(); //吃掉回车 for(i=0;ivernum;i++){ //getchar(); //吃掉回车 G->vers[i].data=getchar(); getchar(); //scanf("%c",&G->vers[i].data); } //初始化图头结点指针和入度值 for(i=0;ivernum;i++){ G->vers[i].firstedge = NULL; G->vers[i].in = 0; //入度为0 } printf("输入边：\n"); for(i=0;ivernum;i++){ scanf("%d %d",&m, &n); struct EdgeNode *newNode = (struct EdgeNode*)malloc(sizeof(struct EdgeNode)); newNode->next = G->vers[m].firstedge == NULL ? NULL : G->vers[m].firstedge; newNode->adjvex = n; G->vers[m].firstedge = newNode; G->vers[n].in++; //入度+1 } } int main(){ struct Graph *G=(struct Graph*)malloc(sizeof(struct Graph)) ; CreateGraph(G); if(TopologicalSort(G)){ printf("拓扑排序完成！\n"); }else{ printf("图存在环"); } return 0; }