算法提升：图的拓扑排序算法

目录

概念

思路

代码

概念

拓扑序列：一些活动，其中某些活动必须在另一些活动完成之后才能开始，一定是无环的有向图，称为AOV网。

拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果：如果此网的全部结点都被输出，则说明其为不存在环的AOV网。如果没有输出全部顶点数，则说明这个网存在回路，不是AOV网。

拓扑排序基本思路：从AOV网中选择一个入度为0的顶点输出，然后删去此结点，并删除以此结点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。

总结一下大概有如下特性：

拓扑排序排的是依赖关系，如果存在环形依赖就没有拓扑序；入度为0的顶点不一定唯一，拓扑排序的结果不一定是唯一；拓扑点值较大的点，在拓扑序中排在前面；

思路

如何用代码实现计算图的拓扑序呢？

给每一个点设置一个入度；把入度为0的点删除掉，把和他关联的其他的点的入度 -1；找到下一个入度为0的点，参考第二部；直到所有的点都被删除掉删除顺序就是拓扑序；

代码

//拓扑排序void TopologicalSort2(GraphLnk *g){int n = g->NumVertices;//创建辅助数组int *count = (int *)malloc(sizeof(int)*n);assert(count != NULL);//初始化辅助数组for (int i = 0; i < n; i ++) {count[i] = 0;}//统计每个顶点的初始入度Edge *p;for (int i = 0; i < n; i ++) {p = g->NodeTable[i].adj;while (p != NULL) {//遍历本顶点的边列表，获取到边的另一个顶点的下标//则另一个顶点的入度加一count[p->dest] ++;p = p->Link;}}//初始化栈SeqStack stack;InitStack(&stack);for (int i = 0; i < n; i ++) {//将初始时每个入度为0的顶点都入栈if (count[i] == 0) {//入栈Push(&stack, i);}}int v,w;//每个顶点依次出栈for (int i = 0; i < n; i ++) {if (IsEmpty(&stack)) {//在小于n时栈就空了，说明有回路printf("网络中有回路\n");return;}else{//获取栈顶元素GetTop(stack, &v);//栈顶元素出栈Pop(&stack);//访问本顶点printf("%2c",g->NodeTable[v].data);//删除所有以本顶点为结尾的弧->本顶点的所有邻接顶点入度减一//获取第一个邻接顶点w = GetFirstNeighbor(g, g->NodeTable[v].data);while(w != -1) {if (--count[w] == 0) {//邻接顶点减一后入度为零，入栈Push(&stack, w);}//获取下一个邻接顶点w = GetNextNeighbor(g, g->NodeTable[v].data, g->NodeTable[w].data);}}}free(count);}