拓扑排序
1、堆栈 栈是一种特殊的线性表，插入或删除栈元素的运算只能在表的一端进行，称运算的一端为栈顶，另一端称为栈底。队列也是一种特殊的线性表（基本操作都是线性操作的子集）。 特点：后进先出 栈又称为“后进先出”的线性表，简称LIFO表。 栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链栈。 2、有向无环图 描述含有公共子式的表达式的有效工具； 描述一项工程或系统的进行过程的有效工具。 3、一些概念 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。 我们用一种有向图来表示这些工程、计划等，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种用顶点表示活动，用弧来表示活动间的优先关系的有向图叫做顶点表示活动的网络(Actire On Vertices)简称为AOV网。 拓扑排序： 假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。 在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。 判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。 4、拓扑排序的算法思想 输入AOV网络。令 n 为顶点个数。 （1）在AOV网络中选一个没有直接前驱的顶点，并输出之； （2）从图中删去该顶点, 同时删去所有它发出的有向边； 重复以上步骤，直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。 5、拓扑排序算法的C语言描述 在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组。 为了避免重复检测入度为0的点，另设一栈存放所有入度为0的点。 对于有n个顶点和e条边的有向图而言，for循环中建立入度为0的顶点栈时间为O（n）；若在拓扑排序过程中不出现有向环，则每个顶点出栈、入栈和入度减1的操作在while循环语句中均执行e次，因此拓扑排序总的时间花费为O (n+e)。 6、拓扑排序算法的C语言实现 #include"stdio.h" #define MAX_VERTEX_NUM20 #include"conio.h" #include"stdlib.h" #define STACK_INIT_SIZE16 #define STACKINCREMENT5 typedef int SElemType; typedef charVertexType; typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; //我们依然用邻接表来作图的存储结构 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int info; }ArcNode; //表结点类型 typedef struct VNode{ VertexType data; int count; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM];//头结点 typedef struct{ AdjList vertices; //邻接表 int vexnum,arcnum; }ALGraph; int InitStack(SqStack&S) { S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(-1); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return 1; }//InitStack int Push(SqStack&S,SElemType e) { if((S.top-S.base)>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) exit(-1); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }//if *(S.top)=e; S.top++; return 1; }//Push int Pop(SqStack&S,SElemType &e) { if(S.top==S.base)return 0; --S.top; e=*S.top; return 1; }//Pop int StackEmpty(SqStack&S) { if(S.top==S.base)return 1; else return 0; }//StackEmpty int LocateVex(ALGraphG,char u) { int i; for (i=0;i<G.vexnum;i++) { if(u==G.vertices[i].data) return i; } if (i==G.vexnum) {printf("Error u!\n");exit(1);} return 0; } voidCreateALGraph_adjlist(ALGraph &G) { int i,j,k,w; char v1,v2,enter; ArcNode *p; printf("Input vexnum &arcnum:\n"); scanf("%d",&G.vexnum); scanf("%d",&G.arcnum); printf("Input Vertices(以回车隔开各个数据):\n"); for (i=0;i<G.vexnum;i++) { scanf("%c%c",&enter,&G.vertices[i].data);//注意点，解说 G.vertices[i].firstarc=NULL; }//for printf("InputArcs(v1,v2,w)以回车分开各个数据:\n"); for (k=0;k<G.arcnum;k++) { scanf("%c%c",&enter,&v1); scanf("%c%c",&enter,&v2); //scanf("%d",&w); i=LocateVex(G,v1); j=LocateVex(G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; //p->info = w; p->nextarc=G.vertices[i].firstarc; //前插法,即每次都插入到头结点的后面 G.vertices[i].firstarc=p; printf("Next\n"); }//for return; }//CreateALGraph_adjlist voidFindInDegree(ALGraph &G) { int i,j; for(i=0;i<G.vexnum;i++) { G.vertices[i].count=0; }//for for(j=0;j<G.vexnum;j++) { //G.vertices[i].count++; for(ArcNode*p=G.vertices[j].firstarc;p;p=p->nextarc) G.vertices[p->adjvex].count++; }//for }//FindInDegree int TopoSort(ALGraph&G) { SqStack S; FindInDegree(G); InitStack(S); for(inti=0;i<G.vexnum;i++) if(G.vertices[i].count==0) Push(S,i); int countt=0; while(!StackEmpty(S)) { int i,m; m=Pop(S,i); printf(" %c",G.vertices[i].data); ++countt; for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc) { int k; k=p->adjvex; if(!(--G.vertices[k].count)) Push(S,k); }//for }//while if(countt<G.vexnum) return 0; else return 1; }//TopoSort int main() { ALGraph G; CreateALGraph_adjlist(G); TopoSort(G); return 1; } 7、malloc函数和realloc函数 realloc: void *realloc(void *block, size_t size)，将block所指存储块调整为大小size，返回新块的地址。如能满足要求，新块的内容与原块一致；不能满足要求时返回NULL，此时原块不变。malloc:void *malloc(size_t size)：分配一块足以存放大小为size的存储，返回该存储块的地址，不能满足时返回NULL。
拓扑排序
通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义： 若集合X上的关系是R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 设R是集合X上的偏序（Partial Order）,如果对每个x,y属于X必有xRy 或 yRx，则称R是集合X上的全序关系。 注意： ①若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的。 ②若图中存在有向环，则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。
举例
【例】对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 【例】一本书的作者将书本中的各章节学习作为顶点，各章节的先学后修关系作为边，构成一个有向图。按有向图的拓扑次序安排章节，才能保证读者在学习某章节时，其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序，至少可得到如下的两个(实际远不止两个)拓扑序列：C0，C1，C2，C4，C3，C5，C7，C8，C6和C0，C7，C9，C1，C4，C2，C3，C6，C5。 ⑤当有向图中存在有向环时，拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示，有向边和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划，则找不到该图的拓扑序列(即含有向环)，就意味着该方案或计划是不可行的。 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即入度为零)的顶点，其抽象算法可描述为： NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有入度为0的顶点)do{ 从G中选择一个入度为0的顶点v且输出之； 从G中删去v及其所有出边； } if(输出的顶点数目<|V(G)|) //若此条件不成立，则表示所有顶点均已输出，排序成功。 Error("G中存在有向环，排序失败！")； } 对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0，C1，C2，C4，C3，C5，C7，C9，C6。 注意： 无前趋的顶点优先的拓扑排序算法在具体存储结构下，为便于考察每个顶点的入度，可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间，可设一个栈或队列暂存所有入度为零的顶点： 在开始排序前，扫描对应的存储空间，将入度为零的顶点均入栈(队)。以后每次选入度为零的顶点时，只需做出栈(队)操作即可。 拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
实现的基本方法
拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.
