目录
1. 拓扑序列2. 拓扑排序的实现（以邻接表为例）2.1 基本思想2.2 完整实现代码及运行结果1. 拓扑序列
有向无环图是指一个无环的有向图。有向无环图可用来描述工程或系统的进行过程，如一个工程的施工图、学生课程间的制约关系图等。
用顶点表示活动，用弧表示活动间优先关系的有向无环图，称为顶点表示活动的网，简称AOV-网。
拓扑序列：在有向图G =（V，{E}）中，V中顶点的线性序列（v1,v2,v3,…,vn）称为拓扑序列。如果此序列满足条件：对序列中任意两个顶点vi，vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj之前。
AOV-网的特性：
① 若 vi 为 vj 的先行活动，vj 为 vk 的先行活动，则 vi 必为 vk 的先行活动，即先行关系具有可传递性。
② AOV-网的拓扑序列不唯一。如上图有向无环图的另一个拓扑序列为：C1，C2，C3，C8，C4，C5，C9，C7，C6。
拓扑排序（Topological Sort）的基本思想：
① 从有向图中选择一个无前驱的结点输出；
② 将此结点和以它为起点的边删除；
③ 重复①、②直到不存在无前驱的结点；
④ 若此时输出的结点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。
示例：
2. 拓扑排序的实现（以邻接表为例）
2.1 基本思想
入度为0的顶点即没有前驱的顶点，对于邻接表结构可以附设一个存放各顶点入度的数组indegree[]，于是有：
① 找G中无前驱的结点——查找indegree[i]为0的顶点i；
② 删除以 i 为起点的所有弧——对链在顶点 i 后面的所有邻接顶点 k，将对应的indegree[k]减1；
（注：若存储结构为邻接矩阵，则
① 找G中无前驱的结点——在邻接矩阵中找到值全为0的列；
② 删除以 i 为起点的所有弧——将矩阵中 i 对应的行全部置为0；）
为避免重复检测入度为0的顶点，可以设置一个辅助栈，若某一顶点的入度减为0，则将它入栈，每当输出某一顶点时，便将它从栈中删除，即出栈。
2.2 完整实现代码及运行结果
# include<stdio.h># include<malloc.h># define MAX_VERTEX_NUM 20# define TRUE 1# define FALSE 0/*图的邻接表表示法*/typedef char VertexData;//弧结点结构typedef struct ArcNode {int adjvex;//该弧指向顶点的位置struct ArcNode* nextarc;//指向下一条弧的指针}ArcNode;//表头结点结构typedef struct VertexNode {VertexData data;//顶点数据ArcNode* firstarc;//指向该顶点的第一条弧的指针}VertexNode;//邻接表结构typedef struct {VertexNode vertex[MAX_VERTEX_NUM];int vexnum, arcnum;//图的顶点数和弧数}AdjList;/*求顶点位置*/int LocateVertex(AdjList* G, VertexData v) {int k;for (k = 0; k < G->vexnum; k++) {if (G->vertex[k].data == v)break;}return k;}/*创建有向图的邻接表*/int CreateAdjList(AdjList* G) {int i, j, k;VertexData v1, v2;ArcNode* p;printf("输入图的顶点数和弧数：");//输入图的顶点数和弧数scanf("%d%d", &G->vexnum, &G->arcnum);printf("输入图的顶点：");for (i = 0; i < G->vexnum; i++) {//输入图的顶点，初始化顶点结点scanf(" %c", &(G->vertex[i].data));G->vertex[i].firstarc = NULL;}for (k = 0; k < G->arcnum; k++) {printf("输入第%d条弧的两个顶点：", k + 1);scanf(" %c %c", &v1, &v2);//输入一条弧的两个顶点i = LocateVertex(G, v1);j = LocateVertex(G, v2);p = (ArcNode*)malloc(sizeof(ArcNode));//申请新弧结点p->adjvex = j;p->nextarc = G->vertex[i].firstarc;G->vertex[i].firstarc = p;}}/*顺序栈的存储结构，辅助栈*/typedef struct {int elem[MAX_VERTEX_NUM];//用于存放栈中元素的一维数组int top;//存放栈顶元素的下标，top为-1表示空栈}SeqStack;/*初始化顺序栈*/void InitStack(SeqStack* S) {S->top = -1;}/*判空*/int IsEmpty(SeqStack* S) {if (S->top == -1)//栈为空return TRUE;elsereturn FALSE;}/*顺序栈进栈*/int Push(SeqStack* S, int x) {if (S->top == MAX_VERTEX_NUM - 1)//栈已满return FALSE;S->top++;S->elem[S->top] = x;//x进栈return TRUE;}/*顺序栈出栈*/int Pop(SeqStack* S) {if (S->top == -1)//栈为空return FALSE;S->top--;return TRUE;}int indegree[MAX_VERTEX_NUM];//存放各顶点入度/*求各顶点入度算法*/void FindID(AdjList G) {int i;ArcNode* p;for (i = 0; i < G.vexnum; i++)indegree[i] = 0;for (i = 0; i < G.vexnum; i++) {p = G.vertex[i].firstarc;while (p != NULL) {indegree[p->adjvex]++;p = p->nextarc;}}}/*拓扑排序算法*/int TopoSort(AdjList G) {int i, count = 0, k;SeqStack S;ArcNode* p;FindID(G);//求各顶点入度InitStack(&S);//初始化辅助栈for (i = 0; i < G.vexnum; i++) {if (indegree[i] == 0)Push(&S, i);//将入度为0的顶点入栈}while (!IsEmpty(&S)) {i = S.elem[S.top];Pop(&S);printf("%c ", G.vertex[i]);count++;p = G.vertex[i].firstarc;while (p != NULL) {k = p->adjvex;indegree[k]--;//i号顶点的每个邻接点的入度减1if (indegree[k] == 0)Push(&S, k);//若入度减为0则入栈p = p->nextarc;}}if (count < G.vexnum) {printf("该图存在回路！\n");return FALSE;}elsereturn TRUE;}int main() {AdjList G;CreateAdjList(&G);printf("\n拓扑排序：");TopoSort(G);return 0;}
运行结果
参考：耿国华《数据结构——用C语言描述（第二版）》
更多数据结构内容关注我的《数据结构》专栏：/weixin_51450101/category_11514538.html?spm=1001..3001.5482
