使用邻接表和拓扑排序算法求关键路径

下面是一个使用邻接表和拓扑排序算法求关键路径的示例代码：

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

#define MAX_VERTEX_NUM 100
#define INFINITY 65535

// 邻接表中的边结构体
typedef struct ArcNode {
    int adjvex;             // 该边指向的顶点编号
    int weight;             // 该边的权重
    struct ArcNode *next;   // 指向下一条边的指针
} ArcNode;

// 邻接表中的顶点结构体
typedef struct VertexNode {
    int data;               // 顶点编号
    ArcNode *firstarc;      // 指向第一条边的指针
} VertexNode;

// 邻接表结构体
typedef struct {
    VertexNode vertices[MAX_VERTEX_NUM];    // 顶点数组
    int vexnum, arcnum;                     // 顶点数和边数
} ALGraph;

// 拓扑排序中的栈结构体
typedef struct {
    int *data;  // 存储栈中的元素
    int top;    // 栈顶指针
    int size;   // 栈的最大容量
} Stack;

// 创建邻接表
void createGraph(ALGraph *G)
{
    int i, j, k, weight;
    ArcNode *p;

    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);

    // 初始化邻接表
    for (i = 0; i < G->vexnum; i++) {
        G->vertices[i].data = i;
        G->vertices[i].firstarc = NULL;
    }

    // 读入边的信息，建立邻接表
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入边的起点、终点和权重：");
        scanf("%d %d %d", &i, &j, &weight);

        // 添加一条从i到j的边
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = weight;
        p->next = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

// 拓扑排序
int topologicalSort(ALGraph G, int ve[])
{
    int i, j;
    int count = 0;
    int indegree[MAX_VERTEX_NUM] = {0}; // 存储每个顶点的入度
    int *stack = (int *)malloc(sizeof(int) * G.vexnum); // 存储拓扑排序中的顶点
    int top = -1;

    // 计算每个顶点的入度
    for (i = 0; i < G.vexnum; i++) {
        for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->next) {
            indegree[p->adjvex]++;
        }
    }

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

    // 依次弹出栈顶顶点，更新其邻接点的入度，入度为0的顶点入栈
    while (top != -1) {
        i = stack[top--];
        count++;

        // 更新所有以i为起点的邻接点的入度
        for (ArcNode *p = G.vertices[i].firstarc; p != NULL; p = p->next) {
            j = p->adjvex;
            if (--indegree[j] == 0) {
                stack[++top] = j;
            }

            // 更新该邻接点的最早开始时间
            if (ve[i] + p->weight > ve[j]) {
                ve[j] = ve[i] + p->weight;
            }
        }
    }

    if (count != G.vexnum) {
        return 0; // 有环
    } else {
        return 1; // 无环
    }
}

// 计算关键路径
void criticalPath(ALGraph G)
{
    int i, j;
    int vl[MAX_VERTEX_NUM]; // 存储每个顶点的最晚开始时间
    int ve[MAX_VERTEX_NUM] = {0}; // 存储每个顶点的最早开始时间
    ArcNode *p;

    // 计算每个顶点的最早开始时间
    if (!topologicalSort(G, ve)) {
        printf("该图存在环，无法计算关键路径！\n");
        return;
    }

    // 计算每个顶点的最晚开始时间
    for (i = 0; i < G.vexnum; i++) {
        vl[i] = ve[G.vexnum - 1];
    }
    for (i = G.vexnum - 2; i >= 0; i--) {
        for (p = G.vertices[i].firstarc; p != NULL; p = p->next) {
            j = p->adjvex;
            if (vl[j] - p->weight < vl[i]) {
                vl[i] = vl[j] - p->weight;
            }
        }
    }

    // 输出关键路径
    printf("关键路径为：");
    for (i = 0; i < G.vexnum; i++) {
        for (p = G.vertices[i].firstarc; p != NULL; p = p->next) {
            j = p->adjvex;
            if (ve[i] + p->weight == vl[j]) {
                printf("%d->%d ", i, j);
            }
        }
    }
    printf("\n");
}

int main()
{
    ALGraph G;

    createGraph(&G);
    criticalPath(G);

    return 0;
}

在该示例代码中，使用拓扑排序算法计算每个顶点的最早开始时间和最晚开始时间，并根据它们的差值来找到关键路径。在实际应用中，还需要考虑多个关键路径的情况，以及如何处理并发活动等问题。