首页 > 代码库 > 拓扑排序
拓扑排序
拓扑排序：
一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。
一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。如图3-6是一个具有三个顶点的回路，由<A,B>边可得B活动必须在A活动之后，由<B,C>边可得C活动必须在B活动之后，所以推出C活动必然在A活动之后，但由<C,A>边可得C活动必须在A活动之前，从而出现矛盾，使每一项活动都无法进行。这种情况若在程序中出现，则称为死锁或死循环，是应该必须避免的。
在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。
实现代码：
#include <stdio.h>#include <stdlib.h>#define MAXVERTEX 20#define INCSIZE 10typedef int ElemType;typedef char VertexType;typedef int EdgeType;typedef struct EdgeNode{ int adjvex; EdgeType weight; struct EdgeNode *next;}EdgeNode;typedef struct VertexNode{ VertexType data; int in; struct EdgeNode *first;}VertexNode,AdjList[MAXVERTEX];typedef struct AdjGraphList{ AdjList adjList; int numVertex; int numEdge;}AdjGraphList;typedef struct SqStack{ ElemType *base; ElemType *top; int stackSize;}SqStack;typedef struct SqStack *LinkStack;//建立一个栈void InitStack(SqStack *s){ s->base = (ElemType *)malloc(MAXVERTEX*sizeof(ElemType)); if(!s->base) return; s->top = s->base; s->stackSize = MAXVERTEX;}void Push(SqStack *s,ElemType *e){ if(s->top - s->base >= s->stackSize - 1) { s->base = (ElemType *)realloc(s->base,(s->stackSize + INCSIZE)*sizeof(ElemType)); if(!s->base) return; } *(s->top) = *e; s->top++;}void Pop(SqStack *s,ElemType *e){ if(s->top == s->base) { return; } s->top--; *e = *(s->top);}int StackLen(SqStack *s){ return (s->top - s->base);}void CreateAdjGraphList(AdjGraphList *G){ int i = 0,j = 0,k = 0,w = 0; int indegree; EdgeNode *p; VertexType c; printf("请输入顶点数和边数，中间用逗号隔开：\n"); scanf("%d,%d",&G->numVertex,&G->numEdge); fflush(stdin); printf("请输入各个顶点存放的值，以及他们的入度,输入#表示结束 :\n"); scanf("%c,%d",&c,&indegree); while(i < G->numVertex) { if(c == ‘#‘) break; G->adjList[i].data = http://www.mamicode.com/c;"请输入各个顶点存放的值，以及他们的入度，输入#表示结束 :\n"); scanf("%c,%d",&c,&indegree); } fflush(stdin); for(k = 0;k < G->numEdge;k++) { printf("请输入边<Vi-Vj>所依附顶点的下标 i 和 j:\n"); scanf("%d,%d",&i,&j); p = (EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex = j; p->next = G->adjList[i].first; G->adjList[i].first = p; }}void AovSort(AdjGraphList *G){ int i = 0,count = 0,k = 0; ElemType e; EdgeNode *q; SqStack s; InitStack(&s); for(i = 0;i < G->numVertex;i++) { if(G->adjList[i].in == 0) { Push(&s,&i); } } while(StackLen(&s)) { Pop(&s,&e); count++; printf("%c->",G->adjList[e].data); q = G->adjList[e].first; while(q) { k = q->adjvex; G->adjList[k].in = G->adjList[k].in - 1; if(G->adjList[k].in == 0) { Push(&s,&k); } q = q->next; } } if(count != G->numVertex) { printf("\n无法继续进行拓扑排序了，检测到AOV网中存在回路！！！\n"); return; } else { printf("End\n"); return; }}int main(){ SqStack s; AdjGraphList G;// InitStack(&s); CreateAdjGraphList(&G); printf("\n拓扑路径为：\n"); AovSort(&G); return 0;}
拓扑排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。