一、基础概念
- 有向无环图 DAG：无回路的有向图，拓扑排序仅对 DAG 有效
- 拓扑排序对 DAG 顶点排序，使得：任意有向边 <u , v> ，u 一定排在 v 前面
- 作用
- 判断有向图是否有环
- 任务调度、课程先后顺序、工程流程
- 特点
- 拓扑序列不唯一
- 有环图 →不存在拓扑排序
二、算法核心思想（入度表法）
- 统计所有顶点入度
- 选取入度为 0的顶点输出
- 删除该顶点所有出边（对应邻接点入度 -1）
- 重复 2~3，直到全部顶点输出 / 剩余顶点均有入度（有环）
三、完整代码（邻接表 + 拓扑排序 + 判环）
#include <stdio.h> #include <stdlib.h> #define MAXN 105 // 边结点 typedef struct EdgeNode { int adjvex; struct EdgeNode *next; }EdgeNode; // 顶点表 typedef struct Vex { EdgeNode *first; }Vex; Vex G[MAXN]; int in[MAXN]; // 每个顶点入度 int n, m; // n顶点 m边 // 拓扑排序 void TopSort() { int stack[MAXN], top = 0; int cnt = 0; // 统计输出顶点数 // 1.所有入度为0的点入栈 for(int i = 0; i < n; i++) { if(in[i] == 0) stack[top++] = i; } while(top != 0) { // 取出入度0的顶点 int u = stack[--top]; printf("%d ", u); cnt++; // 遍历u的所有出边 EdgeNode *p = G[u].first; while(p != NULL) { int v = p->adjvex; in[v]--; // 删除边<u,v>，v入度-1 if(in[v] == 0) stack[top++] = v; p = p->next; } } // 判环 if(cnt != n) printf("\n该有向图存在环，无合法拓扑序列\n"); else printf("\n拓扑排序完成\n"); } // 建图 void InitGraph() { for(int i = 0; i < n; i++) { G[i].first = NULL; in[i] = 0; } } void AddEdge(int u, int v) { EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = v; e->next = G[u].first; G[u].first = e; in[v]++; // 终点入度+1 } int main() { scanf("%d%d", &n, &m); InitGraph(); for(int i = 0; i < m; i++) { int u, v; scanf("%d%d", &u, &v); AddEdge(u, v); } TopSort(); return 0; }四、关键总结
- 适用：有向无环图 DAG
- 核心操作：入度数组+ 删边减入度
- 判定有环：输出顶点个数 <n
- 时间复杂度：O(n+e)
- 序列不唯一：多个入度为 0 的点，选择顺序任意
