求图的关键路径邻接矩阵C语言

求图的关键路径是一个常见的图算法问题，可以使用拓扑排序和关键路径算法来解决。下面是一个使用邻接矩阵表示图的C语言代码示例：

#include <stdio.h>
#include <stdbool.h>

#define MaxVertexNum 100

typedef struct {
    int numV; // 顶点数
    int numE; // 边数
    char nameV[MaxVertexNum]; // 顶点的名字
    int dis[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
} MG, *MGraph;

// 拓扑排序
bool TopologicalSort(MGraph G, int indegree[], int ve[]) {
    int count = 0; // 计数，记录已经输出的顶点数
    int queue[MaxVertexNum]; // 用于存储入度为0的顶点
    int front = 0, rear = 0; // 队列的头尾指针

    // 初始化入度数组和队列
    for (int i = 0; i < G->numV; i++) {
        indegree[i] = 0;
    }
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            if (G->dis[i][j] != 0) {
                indegree[j]++;
            }
        }
    }
    for (int i = 0; i < G->numV; i++) {
        if (indegree[i] == 0) {
            queue[rear++] = i;        }
    }

    // 拓扑排序
    while (front != rear) {
        int v = queue[front++]; // 取出一个入度为0的顶点
        count++; // 计数
        for (int w = 0; w < G->numV; w++) {
            if (G->dis[v][w] != 0) {
                if (--indegree[w] == 0) {
                    queue[rear++] = w; // 入度为0的顶点入队列
                }
                if (ve[v] + G->dis[v][w] > ve[w]) {
                    ve[w] = ve[v] + G->dis[v][w]; // 更新最早开始时间
                }
            }
        }
    }

    if (count < G->numV) {
        return false; // 有回路，拓扑排序失败
    } else {
        return true; // 拓扑排序成功
    }
}

// 关键路径算法
void CriticalPath(MGraph G) {
    int indegree[MaxVertexNum]; // 入度数组
    int ve[MaxVertexNum]; // 最早开始时间
    int vl[MaxVertexNum]; // 最晚开始时间
    int e[MaxVertexNum][MaxVertexNum]; // 事件最早发生时间
    int l[MaxVertexNum][MaxVertexNum]; // 事件最晚发生时间

    // 初始化最早开始时间和最晚开始时间
    for (int i = 0; i < G->numV; i++) {
        ve[i] = 0;
        vl[i] = ve[G->numV - 1];
    }

    // 求最早开始时间
    TopologicalSort(G, indegree, ve);

    // 求最晚开始时间
    for (int i = G->numV - 1; i >= 0; i--) {
        int v = G->numV - 1;
        for (int w = 0; w < G->numV; w++) {
            if (G->dis[v][w] != 0) {
                if (vl[w] - G->dis[v][w] < vl[v]) {
                    vl[v] = vl[w] - G->dis[v][w]; // 更新最晚开始时间
                }
            }
        }
    }

    // 求事件最早发生时间和最晚发生时间
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            e[i][j] = ve[i];
            l[i][j] = vl[j] - G->dis[i][j];
        }
    }

    // 输出关键路径
    printf("Critical Path:\n");
    for (int i = 0; i < G->numV; i++) {
        for (int j = 0; j < G->numV; j++) {
            if (G->dis[i][j] != 0 && e[i][j] == l[i][j]) {
                printf("%c -> %c\n", G->nameV[i], G->nameV[j]);
            }
        }
    }
}

int main() {
    MG G;
    G.numV = 6;
    G.numE = 9;
    strcpy(G.nameV, "ABCDEF");
    memset(G.dis, 0, sizeof(G.dis));
    G.dis[0][1] = 3;
    G.dis[0][2] = 2;
    G.dis[1][3] = 2;
    G.dis[1][4] = 3;
    G.dis[2][3] = 1;
    G.dis[2][5] = 3;
    G.dis[3][4] = 4;
    G.dis[3][5] = 2;
    G.dis[4][5] = 1;

    CriticalPath(&G);

    return 0;
}

这段代码实现了求图的关键路径，其中使用了邻接矩阵存储图的结构。首先进行拓扑排序，然后根据拓扑排序的结果计算最早开始时间和最晚开始时间，最后输出关键路径。