拓扑排序算法详讲

article/2025/10/1 7:51:32

经过一天的专研,终于明白了拓扑排序算法,写篇博客记录一下心得.

一.拓扑排序介绍

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网.
设G=(V,E)是一个具有n个顶点的有向图,v中的顶点序列v1,v2…,vn,满足若从顶点到v1到vj有一
条路径,则在顶点序列中顶点vi必须在顶点vj之前,我们称这样的顶点序列为一个拓扑序列.
所谓拓扑排序,其实就是对一个有向图构造拓扑序列的过程,.
构造时会有两个结果,如果此网的全部顶点都被输出,则说明它是不存在环的AOV网;如果输出的顶点数少了,哪怕是少了一个,也说明这个网存在环,不是AOV网.
一个不存在回路的AOV网,我们可以将它应用在各种各样的工程或项目的流程图中,满足各种应用场景的需要,所以实现拓扑排序很有价值.

二.拓扑排序算法实现

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

对于拓扑排序，在排序的过程中需要删除顶点，显然用邻接表会更加方便，因此我们需要为AOV网建立一个邻接表。考虑到算法过程中始终需要查找入度为0的顶点，我们在原来顶点表结点结构中，需要增加一个入度域in，结构如表所示，其中in就是入读的数字。

有了上面的介绍我们就可以把下面的AOV图转换为邻接表数据结构

#define MAXPOINT 100typedef struct EdgeNode  //边表结点
{int index;  //邻接点的下标,struct EdgeNode * next;   //链域,指向下一个邻接点int weight;                  //权值
}EdgeNode;typedef struct PointNode   //顶点表结点
{int in;                  //顶点入度.int data;                  //顶点信息EdgeNode *  firstEdge;   //边表头指针.   
}PointNode;typedef struct Graph
{int NumPoint, NumEdge;PointNode arr[MAXPOINT];
}Graph;void CreateGraph(Graph * G)
{int i, j, k;EdgeNode* e;printf("请输入顶点和弧的数目:\n");scanf("%d %d", &G->NumPoint, &G->NumEdge);printf("请输入各个顶点的信息:\n");for (i = 0; i < G->NumPoint; i++){scanf("%d", &G->arr[i].data);G->arr[i].in=0;G->arr[i].firstEdge = NULL;}for (k = 0; k < G->NumEdge; k++){printf("请输入弧<vi,vj>上的信息:\n");scanf("%d %d", &i, &j);e = (EdgeNode*)malloc(sizeof(EdgeNode));e->index = j;e->next = G->arr[i].firstEdge;G->arr[i].firstEdge = e;G->arr[j].in++;}
}
int ToupuSort(Graph* G)
{//我们需要辅助的数据结构-栈,  用来存储处理过程中入度为0的顶点//目的是为了避免每个查找时都要全部遍历顶点表找入度为0的顶点.EdgeNode *e;int i,  k, gettop;int top = -1;int count = 0;int * stack;stack = (int *)malloc(sizeof(int)*G->NumPoint);for (i = 0; i < G->NumPoint; i++){if (G->arr[i].in == 0)stack[++top] = i;}while (top != -1){gettop = stack[top--];printf("%d->", G->arr[gettop].data);count++;for (e = G->arr[gettop].firstEdge; e; e = e->next){k = e->index;if (!(--G->arr[k].in))stack[++top] = k;}}if (count < G->NumPoint)return -1;elsereturn 0;}int main()
{Graph G;CreateGraph(&G);ToupuSort(&G);system("pause");return 0;}