用c语言写一个输出关键路径 功能描述：根据创建的有向图及权重，调用TopologicalSort函数应用栈结构输出关键路径。 输出格式printf("Criticalpath: <%d,%d> length: %d\n", 开始节点数组index下标, 下一节点数组index下标, 权重);3 参数描述：ALGraph型参数G 返回值说明：返回关键路径

以下是一个可能的实现，仅供参考：

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF INT_MAX // 定义正无穷

typedef struct EdgeNode {
    int adjvex; // 邻接点下标
    int weight; // 权值
    struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;

typedef struct VertexNode {
    int data; // 顶点的数据
    EdgeNode *firstedge; // 指向第一条边的指针
} VertexNode;

typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM]; // 邻接表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 拓扑排序
int TopologicalSort(ALGraph *G, int *etv) {
    int i, j, k, count;
    int indegree[MAX_VERTEX_NUM]; // 入度数组
    int stack[MAX_VERTEX_NUM]; // 栈
    int top = -1; // 栈顶指针

    for (i = 0; i < G->vexnum; i++) {
        indegree[i] = 0; // 初始化入度数组
    }

    // 统计每个顶点的入度
    for (i = 0; i < G->vexnum; i++) {
        EdgeNode *p = G->adjlist[i].firstedge;
        while (p != NULL) {
            indegree[p->adjvex]++;
            p = p->next;
        }
    }

    // 将入度为0的顶点入栈
    for (i = 0; i < G->vexnum; i++) {
        if (indegree[i] == 0) {
            stack[++top] = i;
        }
    }

    count = 0; // 计数器，记录输出的顶点数
    while (top != -1) {
        i = stack[top--]; // 弹出一个入度为0的顶点
        printf("%d ", i); // 输出该顶点
        count++;

        // 更新与该顶点相邻的顶点的入度
        EdgeNode *p = G->adjlist[i].firstedge;
        while (p != NULL) {
            k = p->adjvex;
            if (--indegree[k] == 0) {
                stack[++top] = k;
            }
            if (etv[i] + p->weight > etv[k]) {
                etv[k] = etv[i] + p->weight;
            }
            p = p->next;
        }
    }

    if (count < G->vexnum) {
        return 0; // 拓扑排序失败，有环
    } else {
        return 1; // 拓扑排序成功，无环
    }
}

// 关键路径算法
void CriticalPath(ALGraph *G) {
    int i, j, k;
    int etv[MAX_VERTEX_NUM]; // 事件最早发生时间
    int ltv[MAX_VERTEX_NUM]; // 事件最晚发生时间
    int stack[MAX_VERTEX_NUM]; // 栈
    int top = -1; // 栈顶指针
    EdgeNode *p;

    // 初始化事件最早发生时间
    for (i = 0; i < G->vexnum; i++) {
        etv[i] = 0;
    }

    // 拓扑排序，计算事件最早发生时间
    if (!TopologicalSort(G, etv)) {
        printf("Error: the graph has a cycle.\n");
        return;
    }

    // 初始化事件最晚发生时间
    for (i = 0; i < G->vexnum; i++) {
        ltv[i] = etv[G->vexnum - 1];
    }

    // 逆拓扑排序，计算事件最晚发生时间
    while (top != -1) {
        i = stack[top--];
        p = G->adjlist[i].firstedge;
        while (p != NULL) {
            k = p->adjvex;
            if (ltv[k] - p->weight < ltv[i]) {
                ltv[i] = ltv[k] - p->weight;
            }
            p = p->next;
        }
    }

    // 计算每条边的最早开始时间和最晚开始时间，找出关键路径
    for (i = 0; i < G->vexnum; i++) {
        p = G->adjlist[i].firstedge;
        while (p != NULL) {
            j = p->adjvex;
            int e = etv[i]; // 最早开始时间
            int l = ltv[j] - p->weight; // 最晚开始时间
            if (e == l) {
                // 该边属于关键路径
                printf("Criticalpath: <%d,%d> length: %d\n", i, j, p->weight);
            }
            p = p->next;
        }
    }
}

int main() {
    ALGraph G;

    // 构造有向图
    G.vexnum = 10;
    G.arcnum = 12;
    for (int i = 0; i < G.vexnum; i++) {
        G.adjlist[i].data = i;
        G.adjlist[i].firstedge = NULL;
    }
    int edges[][3] = {{0, 1, 3}, {0, 2, 4}, {1, 3, 5}, {1, 4, 6}, {2, 3, 8}, {2, 4, 7}, {3, 5, 9}, {3, 6, 11}, {4, 6, 10}, {5, 7, 13}, {6, 7, 12}, {7, 8, 5}};
    for (int i = 0; i < G.arcnum; i++) {
        int u = edges[i][0], v = edges[i][1], w = edges[i][2];
        EdgeNode *p = (EdgeNode *) malloc(sizeof(EdgeNode));
        p->adjvex = v;
        p->weight = w;
        p->next = G.adjlist[u].firstedge;
        G.adjlist[u].firstedge = p;
    }

    // 输出关键路径
    CriticalPath(&G);

    return 0;
}