基于 C 语言的拓扑排序实现
拓扑排序是针对有向无环图（DAG, Directed Acyclic Graph）的一种排序方式，它将图中的
顶点排成一个线性序列，使得对于任意一条从顶点 u 到顶点 v 的有向边(u, v)，顶点 u 都在
顶点 v 之前。拓扑排序不是唯一的，可能存在多个拓扑排序结果。
在 C 语言中实现拓扑排序，常用的方法是 Kahn 算法。Kahn 算法的基本思想是：
从图中选择一个没有前驱（即入度为 0）的顶点输出。
从图中删除该顶点和所有以它为起点的有向边。
重复上述两步，直到所有顶点都被输出（或者图中的所有边都被删除），或者图中不存在入
度为 0 的顶点为止。如果图中不存在环，并且包含 n 个顶点，则最终会输出 n 个顶点；如
果输出顶点数少于 n，则说明图中存在环，无法进行拓扑排序。
以下是使用 C 语言实现 Kahn 算法的拓扑排序示例代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// 使用邻接表表示图
int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示法（这里仅为示例，实际实
现中未使用）
int inDegree[MAX_VERTICES]; // 记录每个顶点的入度
int queue[MAX_VERTICES]; // 用于拓扑排序的队列
int front = 0, rear = -1; // 队列的头和尾指针
// 初始化队列
void initQueue() {
front = 0;
rear = -1;
}
// 入队操作
void enqueue(int vertex) {
if (rear == MAX_VERTICES - 1) {
printf("Queue is full");
return;
}
rear++;
queue[rear] = vertex;
}
资源评论
