C语言实现拓扑排序算法案例：工程项目任务调度

本文以一个工程项目任务依赖关系为例，使用C语言实现了拓扑排序算法，并附带详细的代码解释和示例。通过该案例，您可以理解拓扑排序的原理和应用场景，并学习如何使用C语言实现拓扑排序算法。

案例描述

假设有一个工程项目，其中包含了多个任务，这些任务之间存在依赖关系。每个任务都有一个唯一的编号，并且任务之间的依赖关系可以用有向边表示。如果任务A依赖于任务B，则存在一条从任务B指向任务A的有向边。现在需要对这些任务进行拓扑排序，以确定任务的执行顺序。

C语言代码实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_TASKS 100

// 结点定义
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 图定义
typedef struct Graph {
    int numTasks;
    Node* adjList[MAX_TASKS];
    int inDegree[MAX_TASKS];
} Graph;

// 创建结点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int numTasks) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    if (graph == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    graph->numTasks = numTasks;
    for (int i = 0; i < numTasks; i++) {
        graph->adjList[i] = NULL;
        graph->inDegree[i] = 0;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    if (src < 0 || src >= graph->numTasks || dest < 0 || dest >= graph->numTasks) {
        printf("无效的结点！\n");
        return;
    }
    Node* newNode = createNode(dest);
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
    graph->inDegree[dest]++;
}

// 拓扑排序
void topologicalSort(Graph* graph) {
    int* result = (int*)malloc(graph->numTasks * sizeof(int));
    if (result == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    int front = 0;
    int rear = 0;
    int* queue = (int*)malloc(graph->numTasks * sizeof(int));
    if (queue == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }

    for (int i = 0; i < graph->numTasks; i++) {
        if (graph->inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    int count = 0;
    while (front != rear) {
        int currentTask = queue[front++];
        result[count++] = currentTask;

        Node* temp = graph->adjList[currentTask];
        while (temp != NULL) {
            graph->inDegree[temp->data]--;
            if (graph->inDegree[temp->data] == 0) {
                queue[rear++] = temp->data;
            }
            temp = temp->next;
        }
    }

    if (count != graph->numTasks) {
        printf("存在环路，无法进行拓扑排序！\n");
        return;
    }

    printf("拓扑排序结果：");
    for (int i = 0; i < count; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
    free(queue);
}

int main() {
    int numTasks = 6;
    Graph* graph = createGraph(numTasks);
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    topologicalSort(graph);

    return 0;
}

运行结果

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

结果解释

这表示任务0最先执行，然后是任务1、3、2依次执行，最后是任务4和5同时执行。

总结

本案例通过一个工程项目任务依赖关系的例子，演示了如何使用C语言实现拓扑排序算法。该算法可以用于解决各种需要确定任务执行顺序的问题，例如编译器优化、程序调度等。