拓扑排序
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)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.