AOE网图的拓扑排序与关键路径

AOE网图是指活动在事件之间依赖关系构成的网络图，其中“AOE”是Activity on Edge的缩写。拓扑排序和关键路径是AOE网图中常用的两种算法。

拓扑排序是一种将有向无环图（DAG）中所有顶点排成线性序列的算法。这个序列满足对于任意的有向边 (u, v)，在序列中顶点 u 出现在顶点 v 的前面。拓扑排序可以用来判断一个有向图是否是有环图，也可以用来解决一些依赖关系问题。

关键路径是指在一个AOE网图中，从起始事件到终止事件的所有路径中，最长路径所经过的事件集合。关键路径的长度即为完成整个项目所需的最短时间。关键路径是在拓扑排序的基础上求得的，需要先计算出每个事件的最早发生时间和最迟发生时间，然后根据这些时间计算出每个事件的“浮动时间”，并且找出浮动时间为0的事件序列，这些事件组成了关键路径。

在实际项目管理中，拓扑排序和关键路径常用于计划和控制项目进度，以及确定项目中的关键任务和资源分配。

相关问题

aoe网图的拓扑排序与关键路径

AOE网图是指活动在事件之间依赖关系构成的网络图，其中“AOE”是Activity on Edge的缩写。拓扑排序和关键路径是AOE网图中常用的两种算法。

拓扑排序是一种将有向无环图（DAG）中所有顶点排成线性序列的算法。这个序列满足对于任意的有向边 (u, v)，在序列中顶点 u 出现在顶点 v 的前面。拓扑排序可以用来判断一个有向图是否是有环图，也可以用来解决一些依赖关系问题。

关键路径是指在一个AOE网图中，从起始事件到终止事件的所有路径中，最长路径所经过的事件集合。关键路径的长度即为完成整个项目所需的最短时间。关键路径是在拓扑排序的基础上求得的，需要先计算出每个事件的最早发生时间和最迟发生时间，然后根据这些时间计算出每个事件的“浮动时间”，并且找出浮动时间为0的事件序列，这些事件组成了关键路径。

在实际项目管理中，拓扑排序和关键路径常用于计划和控制项目进度，以及确定项目中的关键任务和资源分配。

AOE网图的拓扑排序与关键路径用c语言写，且面对数据结构初学者

好的，让我们先来了解一下什么是拓扑排序和关键路径。

拓扑排序是对有向无环图（DAG）进行排序的一种方法。它可以将一个DAG的顶点排成一条线性序列，使得对于任何一条有向边 (u, v)，顶点 u 在序列中都排在顶点 v 的前面。

关键路径是指在一个有向无环图中，从起点到终点的所有路径中，耗时最长的那条路径。在实际应用中，关键路径可以用来确定项目的最短工期，以及哪些任务是关键任务，不能延误。

下面是用C语言实现拓扑排序和关键路径的代码，注释中有详细的解释。

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

#define MAX_VERTEX_NUM 100 // 图中最大顶点数
#define MAX_EDGE_NUM 100 // 图中最大边数

// 边的结构体，包含起点和终点
typedef struct {
    int from; // 起点
    int to; // 终点
} Edge;

// 顶点的结构体，包含入度和出度
typedef struct {
    int in; // 入度
    int out; // 出度
} Vertex;

// 图的结构体，包含顶点数组、边数组、顶点数和边数
typedef struct {
    Vertex vertices[MAX_VERTEX_NUM]; // 顶点数组
    Edge edges[MAX_EDGE_NUM]; // 边数组
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

// 初始化图
void init_graph(Graph *g) {
    int i;
    g->vertex_num = 0;
    g->edge_num = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        g->vertices[i].in = 0;
        g->vertices[i].out = 0;
    }
}

// 添加边
void add_edge(Graph *g, int from, int to) {
    g->edges[g->edge_num].from = from;
    g->edges[g->edge_num].to = to;
    g->edge_num++;
    g->vertices[from].out++; // 起点出度加1
    g->vertices[to].in++; // 终点入度加1
}

// 拓扑排序
void topological_sort(Graph *g) {
    int i, j, k, n;
    int queue[MAX_VERTEX_NUM]; // 存储入度为0的顶点
    int head = 0, tail = 0; // 队列头和尾
    int count = 0; // 已排序的顶点数
    Edge *e;

    // 将入度为0的顶点加入队列
    for (i = 0; i < g->vertex_num; i++) {
        if (g->vertices[i].in == 0) {
            queue[tail++] = i;
        }
    }

    // 循环直到队列为空
    while (head != tail) {
        n = tail - head; // 当前队列中的顶点数
        for (i = 0; i < n; i++) {
            j = queue[head++]; // 取出队列头
            printf("%d ", j); // 输出已排序的顶点
            count++; // 已排序的顶点数加1
            for (k = 0; k < g->edge_num; k++) {
                e = &g->edges[k];
                if (e->from == j) { // 找到以j为起点的边
                    g->vertices[e->to].in--; // 对应终点的入度减1
                    if (g->vertices[e->to].in == 0) { // 如果终点入度为0，则加入队列
                        queue[tail++] = e->to;
                    }
                }
            }
        }
    }

    if (count < g->vertex_num) { // 如果已排序的顶点数小于总顶点数，则存在环路
        printf("The graph has a cycle\n");
    }
}

// 计算关键路径
void critical_path(Graph *g) {
    int i, j, k, m = 0, n = 0;
    int earliest[MAX_VERTEX_NUM] = {0}; // 存储最早开始时间
    int latest[MAX_VERTEX_NUM] = {0}; // 存储最晚开始时间
    Edge *e;

    // 计算最早开始时间
    for (i = 0; i < g->vertex_num; i++) {
        for (j = 0; j < g->edge_num; j++) {
            e = &g->edges[j];
            if (e->from == i) { // 找到以i为起点的边
                if (earliest[e->to] < earliest[i] + 1) { // 更新终点的最早开始时间
                    earliest[e->to] = earliest[i] + 1;
                }
            }
        }
    }

    // 计算最晚开始时间
    for (i = g->vertex_num - 1; i >= 0; i--) {
        latest[i] = earliest[g->vertex_num - 1]; // 先初始化为总工期
        for (j = 0; j < g->edge_num; j++) {
            e = &g->edges[j];
            if (e->from == i) { // 找到以i为起点的边
                if (latest[i] > latest[e->to] - 1) { // 更新起点的最晚开始时间
                    latest[i] = latest[e->to] - 1;
                }
            }
        }
    }

    printf("The critical path is: ");
    for (i = 0; i < g->edge_num; i++) {
        e = &g->edges[i];
        if (earliest[e->to] - earliest[e->from] == latest[e->to] - latest[e->from]) { // 如果边的最早开始时间和最晚开始时间相等，则为关键边
            printf("(%d,%d) ", e->from, e->to);
            if (earliest[e->to] > m) { // 找到最大的最早开始时间
                m = earliest[e->to];
            }
            if (latest[e->from] < n) { // 找到最小的最晚开始时间
                n = latest[e->from];
            }
        }
    }

    printf("\nThe minimum time to finish the project is %d\n", m - n);
}

int main() {
    Graph g;
    init_graph(&g);
    g.vertex_num = 7; // 设置顶点数
    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 3);
    add_edge(&g, 1, 4);
    add_edge(&g, 2, 3);
    add_edge(&g, 2, 5);
    add_edge(&g, 3, 6);
    add_edge(&g, 4, 6);
    add_edge(&g, 5, 6);
    topological_sort(&g);
    critical_path(&g);
    return 0;
}

上述代码中，我们定义了一个Graph的结构体来表示图，包含顶点数组、边数组、顶点数和边数。同时定义了一个Vertex的结构体来表示顶点，包含入度和出度。定义了一个Edge的结构体来表示边，包含起点和终点。然后分别实现了初始化图、添加边、拓扑排序和计算关键路径的函数。

在main函数中，我们先初始化图，然后添加边，设置顶点数为7。然后调用拓扑排序和计算关键路径的函数来输出结果。

这段代码可能对于数据结构初学者来说有些难度，但是只要认真看注释，理解了拓扑排序和关键路径的原理，就能够理解代码的实现过程。