| 拓扑排序(C语言简单实现) | 您所在的位置：网站首页 › 环状序列c语言 › 拓扑排序(C语言简单实现) |
拓扑排序(C语言简单实现)
|
拓扑排序
本文参考自《大话数据结构》 AOV定义在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Activity On Vertex Network）。AOV网中的弧表示活动之间存在的某种制约关系。不可以存在环路 设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,...,vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则我们称这样的顶点序列为一个拓扑序列。 所谓拓扑排序，就是对一个有向图构造拓扑序列的过程 。构造时有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环（回路）的AOV网；如果输出顶点数少了，哪怕只是少了一个，也说明这个网存在环（回路），不是AOV网。 一个不存在回路的AOV网，我们可以讲它应用在各种各样的工程或项目的流程图中，满足各种应用场景的需要，所以实现拓扑排序的算法就很有价值了。 简单来讲，拓扑排序就是对有向图进行遍历，得到一条包含全部n个结点，n-1条边的序列。现实中，有向图中的结点相当于每个事件，而有向图的边连接的，表示做某件事之前需要做什么事，因为正常的事件流程中，不应该存在要做B事件之前，需要先完成A事件；而要完成A事件之前，需要完成B事件；最终得到的拓扑序列其实就是完成所有事，中间所做事的顺序（个人理解）。 拓扑排序算法对AOV网进行拓扑排序的基本思路是：从AOV网中选择一个入度为0的顶点输出，然后删除此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出所有顶点或AOV网不存在入度为0的顶点为止。 typedef struct EdgeNode{ //边表结点 int adjvex; //邻接点域，存储该顶点对应的下标 int weight; //用于存储权值，对于非网图可以不需要 struct EdgeNode *next; //链域，指向下一个邻接点 }EdgeNode; typedef struct VertexNode{ //顶点表结点 int in; //顶点入度 int data; //顶点域，存储顶点信息 EdgeNode* firstedge; //边表头指针 }VertexNode, AdjList[MAXVEX]; typedef struct{ AdjList adjList; int numVertexes, numEdges; //图中当前顶点数和边数 }graphAdjList, *GraphAdjList;在算法中，还需要辅助的数据结构-栈，用来存储处理过程中入度为0的顶点，目的是为了避免每个查找时都要去遍历顶点表找有没有入度为0的顶点，下面是代码： /* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */ Status TopplogicalSort(GraphAdjList GL){ EdgeNode *e; int i, k, gettop; int top = 0; //用于栈指针下标 int count = 0; //用于统计输出顶点的个数 int *stack; //建栈存储入度为0的顶点 stack = (int *)malloc(GL->numVertexes * sizeof(int)); for(i=0;inumVertexes;i++) if(GL->adjList[i].in == 0) stack[++top] = i; //将入度为0的顶点入栈 while(top != 0){ gettop = stack[top--]; //出栈 printf("%d->",GL->adjList[gettop].data); //打印此顶点 count++; //统计输出顶点数 for(e = GL->adjList[gettop].firstedge;e;e = e->next){ //对此顶点弧表遍历 k = e->adjvex; if(!(--GL->adjList[k].in)) //将k号顶点邻接点的入度减1 stack[++top] = k; //若为0则入栈，以便下次循环输出 } } if(count numVertexes) //如果count小于顶点数，说明存在环 return ERROR; else return OK; }分析整个算法，对一个具有n个顶点e条弧的AOV网来说，将入度为0的顶点入栈的时间复杂度为O(n)，而之后的while循环中，每个顶点进一次栈，出一次栈，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n+e)。 例子
该图中拓扑排序后只存在一条路径：a->b->d->c->e->f，但是如果图中存在多条拓扑路径，那么拓扑结果不唯一。 #include #include #include #define MAXVEX 10 typedef char VerType; //顶点值类型 struct EdgeNode{ int adjvex; //邻接点域，存储该顶点对应的下标 int weight; //用于存储权值，对于非网图可以不需要 EdgeNode* next; //下一个结点 }; struct VertexNode{ int in; //入度 VerType data; //值 EdgeNode* firstedge; //邻接表头指针 }; struct Graph{ VertexNode vers[MAXVEX]; int numVertexes, numEdges; //顶点数和边数 }; /* 拓扑排序，若G没有回路，则输出拓扑排序序列并返回OK，若有回路返回ERROR */ bool TopologicalSort(Graph* G){ EdgeNode* e; int i, k, gettop; int top = 0; //栈指针下标 int count = 0; //统计输出顶点个数 int* stack; //存储入度为0的顶点 stack = (int*)malloc(G->numVertexes * sizeof(int)); for(i = 0;inumVertexes;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 numVertexes) //如果count小于顶点数，说明存在环 return false; else return true; } /* 图初始化 */ void CreateGraph(Graph* G){ int i, m, n; printf("输入顶点数和边数：\n"); scanf("%d,%d",&G->numVertexes, &G->numEdges); printf("输入顶点值：\n"); for(i=0;inumVertexes;i++){ getchar(); //吃掉回车 scanf("%c",&G->vers[i].data); } //初始化图头结点指针和入度值 for(i=0;inumVertexes;i++){ G->vers[i].firstedge = NULL; G->vers[i].in = 0; //入度为0 } printf("输入边：\n"); for(i=0;inumEdges;i++){ scanf("%d,%d",&m, &n); EdgeNode* newNode = (EdgeNode*)malloc(sizeof(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(){ Graph* G = (Graph*)malloc(sizeof(Graph)); CreateGraph(G); if(TopologicalSort(G)){ printf("拓扑排序完成！\n"); }else{ printf("图存在环"); } return 0; }
|
【本文地址】