有向图的拓扑排序和逆拓扑排序实验指导 1基本内容 对于给定的有向工程施工图，找出该工程图的关键活动。C语言代码

以下是一个基于邻接表表示有向图，实现拓扑排序和关键活动计算的 C 语言代码示例：

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

#define MAXV 1000  // 最大顶点数

struct node {
    int v;  // 邻接点编号
    int w;  // 边权值
    struct node *next;  // 指向下一个邻接点的指针
};

struct graph {
    int n;  // 顶点数
    struct node *adj[MAXV];  // 邻接表
};

int indegree[MAXV];  // 入度数组
int earliest[MAXV];  // 最早开始时间数组
int latest[MAXV];    // 最晚开始时间数组

int max(int a, int b) {
    return a > b ? a : b;
}

// 创建有向图
void createGraph(struct graph *g) {
    int u, v, w;
    struct node *p;
    printf("Enter the number of vertices: ");
    scanf("%d", &g->n);
    for (u = 0; u < g->n; u++)
        g->adj[u] = NULL;
    printf("Enter the edges:\n");
    while (scanf("%d%d%d", &u, &v, &w) == 3) {
        p = (struct node *)malloc(sizeof(struct node));
        p->v = v;
        p->w = w;
        p->next = g->adj[u];
        g->adj[u] = p;
        indegree[v]++;
    }
}

// 拓扑排序
void topoSort(struct graph *g) {
    int u, v, w, t, cnt = 0;
    struct node *p;
    int queue[MAXV], front = 0, rear = 0;
    for (u = 0; u < g->n; u++)
        if (indegree[u] == 0)
            queue[rear++] = u;
    while (front < rear) {
        u = queue[front++];
        printf("%d ", u);
        cnt++;
        for (p = g->adj[u]; p != NULL; p = p->next) {
            v = p->v;
            w = p->w;
            indegree[v]--;
            if (indegree[v] == 0)
                queue[rear++] = v;
            earliest[v] = max(earliest[v], earliest[u] + w);
        }
    }
    if (cnt != g->n)
        printf("Graph has a cycle\n");
}

// 计算关键活动
void criticalPath(struct graph *g) {
    int u, v, w;
    struct node *p;
    topoSort(g);
    for (u = 0; u < g->n; u++)
        latest[u] = earliest[g->n - 1];
    while (u-- > 0) {
        for (p = g->adj[u]; p != NULL; p = p->next) {
            v = p->v;
            w = p->w;
            latest[u] = max(latest[u], latest[v] - w);
        }
    }
    printf("Activity   Earliest   Latest     Slack\n");
    for (u = 0; u < g->n; u++) {
        for (p = g->adj[u]; p != NULL; p = p->next) {
            v = p->v;
            w = p->w;
            printf("%d -> %d    %d         %d         %d\n", u, v, earliest[u], latest[v] - w, latest[v] - w - earliest[u]);
        }
    }
}

int main() {
    struct graph g;
    createGraph(&g);
    criticalPath(&g);
    return 0;
}

在实验中，需要根据具体的有向图，修改输入数据和输出格式，以便正确地计算关键活动。