C语言实现拓扑排序算法 - 课程安排示例

本文将介绍使用 C 语言实现拓扑排序算法，并提供一个课程安排的示例，展示如何使用拓扑排序来确定课程的学习顺序。

1. 拓扑排序的概念

拓扑排序是一种对有向无环图（DAG）进行排序的算法，它将图中的节点按拓扑顺序排列，使得对于图中任意一条边 (u, v)，节点 u 在排序中都出现在节点 v 之前。换句话说，拓扑排序将图中的节点排成一个线性序列，该序列满足以下条件：

对于图中任意一条边 (u, v)，节点 u 在序列中出现在节点 v 之前。
如果图中存在多个拓扑排序，则任何一个拓扑排序都是有效的。

2. 拓扑排序的实现

拓扑排序算法通常使用以下步骤来实现：

**初始化入度：** 初始化一个数组，用于记录每个节点的入度（即指向该节点的边的数量）。
**入度为0的节点入队：** 将入度为0的节点入队，这些节点可以作为拓扑排序的起点。
**循环处理：** 循环以下步骤，直到队列为空：
- 从队列中取出一个节点。
- 输出该节点。
- 遍历该节点的所有出边，将其指向的节点的入度减1。如果指向的节点的入度变为0，则将其入队。

3. 课程安排示例

假设我们有一组课程，每门课程可能有一些先修课程，我们需要确定一个合理的学习顺序，使得所有课程都能学完，并且满足先修课程的要求。我们可以使用拓扑排序来解决这个问题。

以下是一个示例代码，展示了如何使用拓扑排序算法来解决课程安排问题： ```c #include #define MAX_COURSES 5

int courses[MAX_COURSES][MAX_COURSES] = { {0, 1, 1, 1, 1}, // 数学课程的先修课程 {0, 0, 1, 1, 1}, // 物理课程的先修课程 {0, 0, 0, 1, 1}, // 化学课程的先修课程 {0, 0, 0, 0, 1}, // 生物课程的先修课程 {0, 0, 0, 0, 0} // 英语课程的先修课程 };

void topologicalSort(int courses[][MAX_COURSES], int n) { int inDegree[MAX_COURSES] = {0}; // 记录每个课程的入度 int queue[MAX_COURSES] = {0}; // 用于存储入度为0的课程 int front = 0, rear = 0; // 队列的头尾指针

// 计算每个课程的入度
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (courses[j][i] == 1) {
            inDegree[i]++;
        }
    }
}

// 将入度为0的课程入队
for (int i = 0; i < n; i++) {
    if (inDegree[i] == 0) {
        queue[rear++] = i;
    }
}

// 拓扑排序
while (front != rear) {
    int course = queue[front++];
    printf("%d ", course + 1); // 输出排序结果

    // 更新相关课程的入度
    for (int i = 0; i < n; i++) {
        if (courses[course][i] == 1) {
            inDegree[i]--;
            if (inDegree[i] == 0) {
                queue[rear++] = i;
            }
        }
    }
}

}

int main() { printf("拓扑排序结果："); topologicalSort(courses, MAX_COURSES); printf("\n");

return 0;

}

</p>
<h2>4. 实验结果</h2>
<p>运行上述代码，输出的拓扑排序结果为：

拓扑排序结果：1 2 3 4 5

</p>
<h2>5. 实验总结</h2>
<p>通过这个实验，我们学习了如何使用 C 语言实现拓扑排序算法，并了解了拓扑排序在解决课程安排问题中的应用。拓扑排序是一种非常实用的算法，它可以用于解决各种问题，例如任务调度、编译器优化等。</