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

本示例演示了如何使用 C 语言实现拓扑排序算法，并以课程安排为例展示了算法的应用。

代码实现

#include <stdio.h>
#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 &lt; n; i++) {
    for (int j = 0; j &lt; n; j++) {
        if (courses[j][i] == 1) {
            inDegree[i]++;
        }
    }
}

// 将入度为0的课程入队
for (int i = 0; i &lt; 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 &lt; 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;

}

实验步骤

1. 定义一个二维数组courses，表示课程之间的先修关系。数组中的每个元素courses[i][j]表示课程i是否是课程j的先修课程。0表示不是，1表示是。
2. 定义一个一维数组inDegree，用于记录每个课程的入度。数组中的每个元素inDegree[i]表示课程i的入度。
3. 定义一个一维数组queue，用于存储入度为0的课程。
4. 计算每个课程的入度。遍历courses数组，对于每个课程i，统计有多少课程依赖于它，即courses[j][i]为1的个数，将结果存入inDegree[i]中。
5. 将入度为0的课程入队。遍历inDegree数组，对于每个课程i，如果inDegree[i]为0，将课程i入队。
6. 进行拓扑排序。使用队列进行广度优先搜索，每次从队列中取出一个课程，输出，并更新相关课程的入度。对于每个入度为0的课程，将其入队。重复该过程，直到队列为空。
7. 在主函数中调用topologicalSort函数，并输出拓扑排序的结果。

实验结果

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

实验分析

根据先修关系，数学课程没有任何先修课程，所以它是第一个被排序的课程。物理课程的先修课程是数学课程，所以它是第二个被排序的课程。以此类推，最后一个被排序的课程是英语课程，它没有任何先修课程。

因此，实验结果验证了拓扑排序算法的正确性。