c语言拓扑排序实现关键路径

C语言实现拓扑排序和关键路径的方法如下：

1. 首先，需要定义一个有向无环图（DAG）来表示工程的活动和依赖关系。可以使用邻接矩阵或邻接表来表示图。

2. 对于拓扑排序，可以使用深度优先搜索（DFS）算法来实现。具体步骤如下：
- 创建一个栈来存储已经访问过的顶点。
- 从任意一个未访问的顶点开始，进行深度优先搜索。
- 在访问一个顶点时，先将其所有未访问的邻居顶点进行递归访问。
- 当一个顶点的所有邻居都被访问过后，将该顶点入栈。
- 最后，栈中的顶点的出栈顺序就是拓扑排序的结果。

3. 对于关键路径的计算，可以使用关键路径方法（Critical Path Method，简称CPM）来实现。具体步骤如下：
- 首先，需要计算每个活动的最早开始时间（Earliest Start Time，简称EST）和最晚开始时间（Latest Start Time，简称LST）。
- EST表示在不延误整个工程的情况下，活动可以开始的最早时间。
- LST表示在不延误整个工程的情况下，活动必须开始的最晚时间。
- 活动的持续时间可以通过预先给定的数据进行计算。
- 最后，通过比较EST和LST，可以确定关键路径上的活动。

以下是一个示例代码，演示了如何使用C语言实现拓扑排序和计算关键路径：

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

#define MAX_SIZE 100

// 邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 创建邻接表节点
Node* createNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建有向无环图
typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

// 初始化有向无环图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));

    int i;
    for (i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

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

// 拓扑排序的辅助函数
void topologicalSortUtil(Graph* graph, int v, int visited[], int stack[], int* top) {
    visited[v] = 1;

    Node* temp = graph->adjLists[v];
    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex])
            topologicalSortUtil(graph, adjVertex, visited, stack, top);
        temp = temp->next;
    }

    stack[++(*top)] = v;
}

// 拓扑排序
void topologicalSort(Graph* graph) {
    int visited[MAX_SIZE] = {0};
    int stack[MAX_SIZE];
    int top = -1;

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

    printf("Topological Sort: ");
    while (top >= 0) {
        printf("%d ", stack[top--]);
    }
    printf("\n");
}

// 计算关键路径
void criticalPath(Graph* graph, int source, int destination) {
    int numVertices = graph->numVertices;
    int* earliestStart = (int*)malloc(numVertices * sizeof(int));
    int* latestStart = (int*)malloc(numVertices * sizeof(int));

    // 初始化最早开始时间和最晚开始时间
    int i;
    for (i = 0; i < numVertices; i++) {
        earliestStart[i] = 0;
        latestStart[i] = INT_MAX;
    }

    // 计算最早开始时间
    topologicalSortUtil(graph, source, earliestStart, NULL, NULL);

    // 计算最晚开始时间
    latestStart[destination] = earliestStart[destination];
    for (i = numVertices - 1; i >= 0; i--) {
        int vertex = earliestStart[i];

        Node* temp = graph->adjLists[vertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (latestStart[adjVertex] - temp->weight < latestStart[vertex])
                latestStart[vertex] = latestStart[adjVertex] - temp->weight;
            temp = temp->next;
        }
    }

    // 打印关键路径上的活动
    printf("Critical Path: ");
    for (i = 0; i < numVertices; i++) {
        if (earliestStart[i] == latestStart[i])
            printf("%d ", i);
    }
    printf("\n");

    free(earliestStart);
    free(latestStart);
}

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

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    // 设置活动的持续时间
    graph->adjLists[0]->weight = 2;
    graph->adjLists[1]->weight = 3;
    graph->adjLists[2]->weight = 1;
    graph->adjLists[3]->weight = 4;
    graph->adjLists[4]->weight = 2;
    graph->adjLists[5]->weight = 3;

    topologicalSort(graph);
    criticalPath(graph, 0, 5);

    return 0;
}