C 语言实现关键路径算法 - 邻接表 - 拓扑排序

#include\x3Cstdio.h\x3E #include\x3Cstdlib.h\x3E

// 邻接表中的节点 struct Node { int task; // 任务编号 int duration; // 任务持续时间 struct Node* next; // 指向下一个节点的指针 };

// 邻接表 struct Graph { int numTasks; // 任务数量 struct Node** adjList; // 邻接表的指针数组 };

// 创建一个节点 struct Node* createNode(int task, int duration) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->task = task; newNode->duration = duration; newNode->next = NULL; return newNode; }

// 创建一个邻接表 struct Graph* createGraph(int numTasks) { struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph)); graph->numTasks = numTasks; graph->adjList = (struct Node**)malloc(numTasks * sizeof(struct Node*)); for (int i = 0; i < numTasks; i++) { graph->adjList[i] = NULL; } return graph; }

// 添加边 void addEdge(struct Graph* graph, int src, int dest, int duration) { struct Node* newNode = createNode(dest, duration); newNode->next = graph->adjList[src]; graph->adjList[src] = newNode; }

// 拓扑排序的递归函数 void topologicalSortUtil(struct Graph* graph, int v, int* visited, int* stack, int* top) { visited[v] = 1; // 标记当前节点为已访问

struct Node* temp = graph->adjList[v];
while (temp != NULL) {
    if (!visited[temp->task]) {
        topologicalSortUtil(graph, temp->task, visited, stack, top);
    }
    temp = temp->next;
}

stack[++(*top)] = v; // 将当前节点压入栈中

}

// 执行拓扑排序 void topologicalSort(struct Graph* graph, int* stack) { int numTasks = graph->numTasks; int visited[numTasks]; int top = -1;

for (int i = 0; i < numTasks; i++) {
    visited[i] = 0; // 初始化visited数组
}

for (int i = 0; i < numTasks; i++) {
    if (!visited[i]) {
        topologicalSortUtil(graph, i, visited, stack, &top);
    }
}

}

// 计算关键路径 void calculateCriticalPath(struct Graph* graph, int* stack, int* est, int* lst) { int numTasks = graph->numTasks;

// 初始化最早开始时间和最晚开始时间数组
for (int i = 0; i < numTasks; i++) {
    est[i] = -1;
    lst[i] = -1;
}

est[0] = 0; // 第一个任务的最早开始时间为0

// 计算最早开始时间
for (int i = 0; i < numTasks; i++) {
    int currentTask = stack[i];
    struct Node* temp = graph->adjList[currentTask];
    while (temp != NULL) {
        if (est[temp->task] < est[currentTask] + temp->duration) {
            est[temp->task] = est[currentTask] + temp->duration;
        }
        temp = temp->next;
    }
}

lst[numTasks-1] = est[numTasks-1]; // 最后一个任务的最晚开始时间等于最早开始时间

// 计算最晚开始时间
for (int i = numTasks-1; i >= 0; i--) {
    int currentTask = stack[i];
    struct Node* temp = graph->adjList[currentTask];
    while (temp != NULL) {
        if (lst[temp->task] - temp->duration < lst[currentTask] || lst[currentTask] == -1) {
            lst[currentTask] = lst[temp->task] - temp->duration;
        }
        temp = temp->next;
    }
}

}

int main() { int numTasks = 6; struct Graph* graph = createGraph(numTasks);

// 添加边
addEdge(graph, 0, 1, 2); // 采购原材料 -> 设计图纸
addEdge(graph, 1, 2, 5); // 设计图纸 -> 制造产品
addEdge(graph, 2, 3, 10); // 制造产品 -> 测试产品
addEdge(graph, 3, 4, 3); // 测试产品 -> 包装产品
addEdge(graph, 4, 5, 2); // 包装产品 -> 发货产品

int stack[numTasks];
topologicalSort(graph, stack);

int est[numTasks];
int lst[numTasks];
calculateCriticalPath(graph, stack, est, lst);

printf("关键路径：");
for (int i = 0; i < numTasks; i++) {
    if (est[i] == lst[i]) {
        printf("%d ", i);
    }
}
printf("\n");

return 0;