拓扑排序与关键路径课设

拓扑排序和关键路径是图论中的两个重要概念，它们在课设中的应用也非常广泛。拓扑排序是指将有向无环图（DAG）中的节点按照一定的顺序进行排序的过程，使得所有的有向边均从排在前面的节点指向排在后面的节点。而关键路径是指在一个有向无环图中，从起点到终点的所有路径中，耗时最长的路径所包含的所有节点构成的路径，这条路径的长度被称为关键路径长度。

在课设中，拓扑排序和关键路径可以被用来解决很多实际问题，例如任务调度、工程进度管理等。具体来说，可以通过拓扑排序来确定任务的执行顺序，通过关键路径来确定整个工程的最短完成时间。

如果你需要实现拓扑排序和关键路径的课设，可以考虑使用C语言来编写程序。你可以使用链表来存储图的节点和边，然后使用拓扑排序算法来对节点进行排序。在排序的过程中，你可以记录每个节点的入度和出度，以及每个节点的最早开始时间和最晚开始时间，这些信息可以用来计算关键路径。最后，你可以使用关键路径算法来计算整个图的关键路径和关键路径长度。

以下是一个简单的C语言程序，用来实现拓扑排序和关键路径的功能。这个程序使用邻接表来存储图的节点和边，然后使用DFS算法来进行拓扑排序和关键路径的计算。

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

#define MAX_VERTEX_NUM 100 // 最大节点数

typedef struct ArcNode { // 边节点
    int adjvex; // 邻接节点编号
    int weight; // 边权重
    struct ArcNode *next; // 指向下一个边节点的指针
} ArcNode;

typedef struct VertexNode { // 节点
    int data; // 节点编号
    int in_degree; // 入度
    int out_degree; // 出度
    int earliest_time; // 最早开始时间
    int latest_time; // 最晚开始时间
    ArcNode *first_arc; // 指向第一个边节点的指针
} VertexNode;

typedef struct { // 图
    VertexNode vertex[MAX_VERTEX_NUM]; // 节点数组
    int vertex_num; // 节点数
    int arc_num; // 边数
} Graph;

void create_graph(Graph *G) { // 创建图
    int i, j, k, w;
    ArcNode *p;
    printf("请输入节点数和边数：");
    scanf("%d%d", &G->vertex_num, &G->arc_num);
    printf("请输入节点编号：");
    for (i = 0; i < G->vertex_num; i++) {
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].in_degree = 0;
        G->vertex[i].out_degree = 0;
        G->vertex[i].earliest_time = 0;
        G->vertex[i].latest_time = 0;
        G->vertex[i].first_arc = NULL;
    }
    printf("请输入边的起点、终点和权重：");
    for (k = 0; k < G->arc_num; k++) {
        scanf("%d%d%d", &i, &j, &w);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->weight = w;
        p->next = G->vertex[i].first_arc;
        G->vertex[i].first_arc = p;
        G->vertex[i].out_degree++;
        G->vertex[j].in_degree++;
    }
}

void topological_sort(Graph *G) { // 拓扑排序
    int i, j, k, count = 0;
    int *stack, top = -1;
    ArcNode *p;
    stack = (int *)malloc(G->vertex_num * sizeof(int));
    for (i = 0; i < G->vertex_num; i++) {
        if (G->vertex[i].in_degree == 0) {
            stack[++top] = i;
        }
    }
    while (top != -1) {
        i = stack[top--];
        printf("%d ", G->vertex[i].data);
        count++;
        for (p = G->vertex[i].first_arc; p != NULL; p = p->next) {
            j = p->adjvex;
            if (--G->vertex[j].in_degree == 0) {
                stack[++top] = j;
            }
        }
    }
    if (count < G->vertex_num) {
        printf("图中存在环\n");
    }
}

void critical_path(Graph *G) { // 关键路径
    int i, j, k, e, l;
    ArcNode *p;
    int *stack, top = -1;
    stack = (int *)malloc(G->vertex_num * sizeof(int));
    for (i = 0; i < G->vertex_num; i++) {
        if (G->vertex[i].in_degree == 0) {
            G->vertex[i].earliest_time = 0;
            stack[++top] = i;
        }
    }
    while (top != -1) {
        i = stack[top--];
        for (p = G->vertex[i].first_arc; p != NULL; p = p->next) {
            j = p->adjvex;
            if (--G->vertex[j].in_degree == 0) {
                stack[++top] = j;
            }
            if (G->vertex[i].earliest_time + p->weight > G->vertex[j].earliest_time) {
                G->vertex[j].earliest_time = G->vertex[i].earliest_time + p->weight;
            }
        }
    }
    for (i = 0; i < G->vertex_num; i++) {
        if (G->vertex[i].out_degree == 0) {
            G->vertex[i].latest_time = G->vertex[i].earliest_time;
        }
    }
    while (top != -1) {
        i = stack[top--];
        for (p = G->vertex[i].first_arc; p != NULL; p = p->next) {
            j = p->adjvex;
            if (G->vertex[j].latest_time - p->weight < G->vertex[i].latest_time) {
                G->vertex[i].latest_time = G->vertex[j].latest_time - p->weight;
            }
        }
    }
    printf("关键路径为：");
    for (i = 0; i < G->vertex_num; i++) {
        for (p = G->vertex[i].first_arc; p != NULL; p = p->next) {
            j = p->adjvex;
            e = G->vertex[i].earliest_time;
            l = G->vertex[j].latest_time - p->weight;
            if (e == l) {
                printf("(%d,%d) ", G->vertex[i].data, G->vertex[j].data);
            }
        }
    }
    printf("\n关键路径长度为：%d\n", G->vertex[G->vertex_num - 1].earliest_time);
}

int main() {
    Graph G;
    create_graph(&G);
    printf("拓扑排序结果为：");
    topological_sort(&G);
    critical_path(&G);
    return 0;
}