使用c语言，采用数组表示法和邻接表存储，实现拓扑排序和关键路径算法

拓扑排序算法：

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

#define MAX_VERTICES 100  // 图中最大顶点数

typedef struct _node {
    int vertex;
    struct _node* next;
} Node;

Node* graph[MAX_VERTICES];  // 邻接表
int in_degree[MAX_VERTICES];  // 每个顶点的入度
int n;  // 顶点数

void add_edge(int u, int v) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->vertex = v;
    node->next = graph[u];
    graph[u] = node;
}

void topological_sort() {
    int i, j, k;
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;  // 队列的头和尾
    Node* node;

    // 计算每个顶点的入度
    for (i = 0; i < n; i++) {
        in_degree[i] = 0;
        for (node = graph[i]; node != NULL; node = node->next) {
            in_degree[node->vertex]++;
        }
    }

    // 将入度为 0 的顶点加入队列
    for (i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 按照拓扑序输出每个顶点
    while (front < rear) {
        i = queue[front++];  // 取出一个入度为 0 的顶点
        printf("%d ", i);

        // 将与该顶点相邻的顶点的入度减 1，并将入度为 0 的顶点加入队列
        for (node = graph[i]; node != NULL; node = node->next) {
            j = node->vertex;
            in_degree[j]--;
            if (in_degree[j] == 0) {
                queue[rear++] = j;
            }
        }
    }
}

int main() {
    int i, u, v, e;

    scanf("%d %d", &n, &e);

    // 初始化邻接表
    for (i = 0; i < n; i++) {
        graph[i] = NULL;
    }

    // 读入边并建图
    for (i = 0; i < e; i++) {
        scanf("%d %d", &u, &v);
        add_edge(u, v);
    }

    topological_sort();

    return 0;
}

关键路径算法：

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

#define MAX_VERTICES 100  // 图中最大顶点数
#define INF INT_MAX

typedef struct _node {
    int vertex;
    int weight;
    struct _node* next;
} Node;

Node* graph[MAX_VERTICES];  // 邻接表
int in_degree[MAX_VERTICES];  // 每个顶点的入度
int n;  // 顶点数
int earliest[MAX_VERTICES];  // 每个顶点的最早开始时间
int latest[MAX_VERTICES];  // 每个顶点的最晚开始时间
int critical[MAX_VERTICES];  // 是否为关键路径上的顶点

void add_edge(int u, int v, int w) {
    Node* node = (Node*) malloc(sizeof(Node));
    node->vertex = v;
    node->weight = w;
    node->next = graph[u];
    graph[u] = node;
}

void topological_sort() {
    int i, j, k;
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;  // 队列的头和尾
    Node* node;

    // 计算每个顶点的入度
    for (i = 0; i < n; i++) {
        in_degree[i] = 0;
        for (node = graph[i]; node != NULL; node = node->next) {
            in_degree[node->vertex]++;
        }
    }

    // 将入度为 0 的顶点加入队列
    for (i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 计算每个顶点的最早开始时间
    while (front < rear) {
        i = queue[front++];  // 取出一个入度为 0 的顶点

        for (node = graph[i]; node != NULL; node = node->next) {
            j = node->vertex;
            if (--in_degree[j] == 0) {
                queue[rear++] = j;
            }
            if (earliest[i] + node->weight > earliest[j]) {
                earliest[j] = earliest[i] + node->weight;
            }
        }
    }
}

int latest_time() {
    int i, j, k;
    int queue[MAX_VERTICES];
    int front = 0, rear = 0;  // 队列的头和尾
    Node* node;

    // 将终点加入队列
    queue[rear++] = n - 1;

    // 计算每个顶点的最晚开始时间
    while (front < rear) {
        i = queue[front++];  // 取出一个顶点

        for (node = graph[i]; node != NULL; node = node->next) {
            j = node->vertex;
            if (latest[j] - node->weight < latest[i]) {
                latest[i] = latest[j] - node->weight;
            }
            if (--in_degree[j] == 0) {
                queue[rear++] = j;
            }
        }
    }

    // 判断每个顶点是否为关键路径上的顶点
    for (i = 0; i < n; i++) {
        critical[i] = (earliest[i] == latest[i]);
    }

    return earliest[n - 1];
}

int main() {
    int i, u, v, w, e;

    scanf("%d %d", &n, &e);

    // 初始化邻接表
    for (i = 0; i < n; i++) {
        graph[i] = NULL;
    }

    // 读入边并建图
    for (i = 0; i < e; i++) {
        scanf("%d %d %d", &u, &v, &w);
        add_edge(u, v, w);
    }

    // 计算每个顶点的最早开始时间
    topological_sort();

    // 计算每个顶点的最晚开始时间，并判断关键路径上的顶点
    printf("Critical path: ");
    printf("%d\n", latest_time());

    // 输出关键路径上的顶点
    for (i = 0; i < n; i++) {
        if (critical[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}