c语言实现有向网的关键路径

关键路径是指在一个有向无环图中，从起点到终点的最长路径。关键路径上的每个节点都是整个图中的关键节点，这些节点的最早开始时间和最迟开始时间相等。

下面是使用 C 语言实现有向网的关键路径的一般步骤：

1. 定义有向网的数据结构，包括节点、边和权值等信息。

2. 构建有向网，读入节点、边和权值等信息，保存到数据结构中。

3. 计算每个节点的最早开始时间（EST）和最迟开始时间（LST）。

4. 计算每条边的最早开始时间（EET）和最迟开始时间（LET）。

5. 根据节点和边的计算结果，确定关键路径上的节点和边，输出关键路径和关键节点。

下面是一个简单的 C 语言示例代码：

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

#define MAX_VERTEX_NUM 100 // 最大节点数量

typedef struct {
    int adj; // 相邻节点编号
    int weight; // 权值
} ArcNode;

typedef struct {
    char name[20]; // 节点名称
    int inDegree; // 入度
    int outDegree; // 出度
    int earliest; // 最早开始时间
    int latest; // 最迟开始时间
    ArcNode *adjList; // 相邻节点列表
} VertexNode;

typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM]; // 节点列表
    int vertexNum; // 节点数量
} Graph;

void initGraph(Graph *G) {
    memset(G, 0, sizeof(Graph));
}

int findVertex(Graph *G, char *name) {
    for (int i = 0; i < G->vertexNum; i++) {
        if (strcmp(G->vertex[i].name, name) == 0) {
            return i;
        }
    }
    return -1;
}

void addVertex(Graph *G, char *name) {
    if (findVertex(G, name) != -1) {
        return;
    }
    strcpy(G->vertex[G->vertexNum].name, name);
    G->vertexNum++;
}

void addEdge(Graph *G, char *start, char *end, int weight) {
    int i = findVertex(G, start);
    int j = findVertex(G, end);
    if (i == -1 || j == -1) {
        return;
    }
    ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
    p->adj = j;
    p->weight = weight;
    p->next = G->vertex[i].adjList;
    G->vertex[i].adjList = p;
    G->vertex[j].inDegree++;
    G->vertex[i].outDegree++;
}

int topologicalSort(Graph *G, int *topoSeq) {
    int n = 0;
    int *inDegree = (int*)malloc(sizeof(int) * G->vertexNum);
    memset(inDegree, 0, sizeof(int) * G->vertexNum);
    for (int i = 0; i < G->vertexNum; i++) {
        inDegree[i] = G->vertex[i].inDegree;
    }
    int *stack = (int*)malloc(sizeof(int) * G->vertexNum);
    int top = -1;
    for (int i = 0; i < G->vertexNum; i++) {
        if (inDegree[i] == 0) {
            stack[++top] = i;
        }
    }
    while (top != -1) {
        int i = stack[top--];
        topoSeq[n++] = i;
        for (ArcNode *p = G->vertex[i].adjList; p; p = p->next) {
            int j = p->adj;
            if (--inDegree[j] == 0) {
                stack[++top] = j;
            }
        }
    }
    free(inDegree);
    free(stack);
    if (n == G->vertexNum) {
        return 1;
    } else {
        return 0;
    }
}

int criticalPath(Graph *G) {
    int *topoSeq = (int*)malloc(sizeof(int) * G->vertexNum);
    if (!topologicalSort(G, topoSeq)) {
        return 0;
    }
    for (int i = 0; i < G->vertexNum; i++) {
        G->vertex[topoSeq[i]].earliest = 0;
    }
    for (int i = 0; i < G->vertexNum; i++) {
        int j = topoSeq[i];
        for (ArcNode *p = G->vertex[j].adjList; p; p = p->next) {
            int k = p->adj;
            int t = G->vertex[j].earliest + p->weight;
            if (t > G->vertex[k].earliest) {
                G->vertex[k].earliest = t;
            }
        }
    }
    int end = topoSeq[G->vertexNum - 1];
    G->vertex[end].latest = G->vertex[end].earliest;
    for (int i = G->vertexNum - 2; i >= 0; i--) {
        int j = topoSeq[i];
        G->vertex[j].latest = G->vertex[end].latest;
        for (ArcNode *p = G->vertex[j].adjList; p; p = p->next) {
            int k = p->adj;
            int t = G->vertex[k].latest - p->weight;
            if (t < G->vertex[j].latest) {
                G->vertex[j].latest = t;
            }
        }
    }
    int critical = 0;
    for (int i = 0; i < G->vertexNum; i++) {
        for (ArcNode *p = G->vertex[i].adjList; p; p = p->next) {
            int j = p->adj;
            int eet = G->vertex[i].earliest;
            int let = G->vertex[j].latest - p->weight;
            if (eet == let) {
                printf("%s -> %s is a critical edge.\n", G->vertex[i].name, G->vertex[j].name);
                critical = 1;
            }
        }
    }
    free(topoSeq);
    return critical;
}

int main() {
    Graph G;
    initGraph(&G);
    addVertex(&G, "A");
    addVertex(&G, "B");
    addVertex(&G, "C");
    addVertex(&G, "D");
    addVertex(&G, "E");
    addEdge(&G, "A", "B", 3);
    addEdge(&G, "A", "C", 2);
    addEdge(&G, "B", "D", 4);
    addEdge(&G, "C", "D", 5);
    addEdge(&G, "B", "E", 6);
    addEdge(&G, "D", "E", 1);
    if (!criticalPath(&G)) {
        printf("There is no critical path.\n");
    }
    return 0;
}

上述代码实现了有向网的关键路径，包括了关键路径上的节点和边的计算，以及输出关键路径和关键节点。