1、实验目的： （1）通过上机掌握图（网）的存储定义、生成、显示； （2）掌握图（网）的拓扑排序与关键路径算法。 2、实验内容： （1）从文件中读入有向图(网)并以邻接表存储； （2）利用 AOE 网络求取其关键路径。 3、实验要求 （1）完成时间：2 学时； （2）上机前首先复习相关知识：关键路径的相关知识 P178-183，顺序栈的相关知识 P57- 59 （3）AOE 网输入：P179 图 6.28，文件输入方式； （4）部份函数见下“实验提示”，函数不一定完整，在下划线上补充相应正确的语句。 其他需要的函数参照教材算法描述自行编程实现；

很好，这是一道关于图的拓扑排序和关键路径算法的实验题目，需要从文件中读入有向图并以邻接表存储，然后利用 AOE 网络求取其关键路径。

在开始编程之前，我们需要复习一下关键路径的相关知识，以及顺序栈的相关知识。同时，我们需要按照题目要求，编写从文件中读取有向图数据的函数，并以邻接表存储。

以下是一些实验提示，希望对你有所帮助：

1. 读取文件中的有向图数据

我们可以使用 C 语言中的文件操作函数来读取文件中的有向图数据。具体来说，我们可以使用 fscanf 函数按照特定格式从文件中读取数据，并将其存储到相应的数据结构中。例如，假设我们的有向图数据格式如下：

4 5
0 1 2
0 2 3
1 2 1
1 3 4
2 3 5

第一行表示有向图的节点数和边数，后面的每一行表示一条有向边，由起始节点、终止节点和权值组成。我们可以使用以下代码来读取并存储这些数据：

// 定义边结构体
struct Edge {
    int start;  // 起始节点
    int end;    // 终止节点
    int weight; // 权值
};

// 从文件中读取有向图数据
void readGraph(char* filename, int* n, int* m, struct Edge* edges) {
    FILE* fp = fopen(filename, "r");
    fscanf(fp, "%d %d", n, m);
    for (int i = 0; i < *m; i++) {
        fscanf(fp, "%d %d %d", &edges[i].start, &edges[i].end, &edges[i].weight);
    }
    fclose(fp);
}

在这个函数中，我们使用了一个结构体 Edge 来存储每条有向边的信息。我们首先打开文件并读取第一行的节点数和边数，然后依次读取每条有向边的信息，并将其存储到 edges 数组中。

2. 邻接表存储有向图

有了从文件中读取数据的函数，我们就可以开始将有向图存储到邻接表中了。邻接表是一种比较常用的图存储方式，它使用一个数组来存储每个节点的出边，每个数组元素对应一个链表，链表中存储该节点的所有出边。为了方便起见，我们可以使用 C 语言中的动态内存分配来实现链表。

以下是一个使用邻接表存储有向图的示例代码：

// 定义邻接表节点结构体
struct AdjListNode {
    int dest;               // 目标节点
    int weight;             // 边权值
    struct AdjListNode* next; // 下一个节点
};

// 定义邻接表结构体
struct AdjList {
    struct AdjListNode* head; // 头节点
};

// 定义有向图结构体
struct Graph {
    int numVertices;        // 节点数
    struct AdjList* adjLists; // 邻接表数组
};

// 创建新的邻接表节点
struct AdjListNode* newAdjListNode(int dest, int weight) {
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 创建有向图
struct Graph* createGraph(int numVertices, struct Edge* edges, int numEdges) {
    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->numVertices = numVertices;
    graph->adjLists = (struct AdjList*) malloc(numVertices * sizeof(struct AdjList));
    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i].head = NULL;
    }
    for (int i = 0; i < numEdges; i++) {
        int start = edges[i].start;
        int end = edges[i].end;
        int weight = edges[i].weight;
        struct AdjListNode* newNode = newAdjListNode(end, weight);
        newNode->next = graph->adjLists[start].head;
        graph->adjLists[start].head = newNode;
    }
    return graph;
}

在这个示例代码中，我们首先定义了一个邻接表节点结构体 AdjListNode，用于表示每个节点的出边。然后定义了一个邻接表结构体 AdjList，用于存储每个节点的所有出边。最后定义了一个有向图结构体 Graph，它由节点数和邻接表数组组成。

我们还定义了一个 newAdjListNode 函数，用于创建一个新的邻接表节点。在 createGraph 函数中，我们首先创建了一个空的有向图，并将每个节点的邻接表初始化为空。然后依次遍历每条有向边，创建新的邻接表节点，并将其添加到起始节点的邻接表中。

3. 拓扑排序算法

有了存储有向图的邻接表，我们就可以开始实现拓扑排序算法了。拓扑排序算法可以用来解决有向无环图中的依赖关系问题，它可以将图中的节点按照依赖关系排成一条线性序列。具体来说，拓扑排序算法可以通过不断删除入度为 0 的节点来依次确定每个节点的排序位置。

以下是一个使用拓扑排序算法对有向图进行排序的示例代码：

// 拓扑排序算法
void topologicalSort(struct Graph* graph, int* sortedVertices) {
    int* indegrees = (int*) malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++) {
        indegrees[i] = 0;
    }
    for (int i = 0; i < graph->numVertices; i++) {
        struct AdjListNode* currentNode = graph->adjLists[i].head;
        while (currentNode != NULL) {
            indegrees[currentNode->dest]++;
            currentNode = currentNode->next;
        }
    }
    int stack[graph->numVertices];
    int top = -1;
    for (int i = 0; i < graph->numVertices; i++) {
        if (indegrees[i] == 0) {
            stack[++top] = i;
        }
    }
    int count = 0;
    while (top != -1) {
        int currentVertex = stack[top--];
        sortedVertices[count++] = currentVertex;
        struct AdjListNode* currentNode = graph->adjLists[currentVertex].head;
        while (currentNode != NULL) {
            int destVertex = currentNode->dest;
            indegrees[destVertex]--;
            if (indegrees[destVertex] == 0) {
                stack[++top] = destVertex;
            }
            currentNode = currentNode->next;
        }
    }
    free(indegrees);
}

在这个示例代码中，我们首先定义了一个 indegrees 数组，用于存储每个节点的入度。然后遍历每个节点的邻接表，统计每个节点的入度。接着，我们使用一个栈来存储当前入度为 0 的节点，并不断删除这些节点，并将其邻居节点的入度减一，直到所有节点都被排序为止。

4. 关键路径算法

有了拓扑排序算法，我们就可以开始实现关键路径算法了。关键路径算法可以用来确定有向无环图中的关键路径，即必须按照该路径才能完成整个项目的所有任务。具体来说，关键路径算法可以通过计算每个节点的最早开始时间和最晚开始时间，来确定每个任务的关键路径和总工期。

以下是一个使用关键路径算法求解有向图关键路径的示例代码：

// 计算关键路径
int criticalPath(struct Graph* graph, int* earliestStart, int* latestStart) {
    // 计算拓扑排序序列
    int sortedVertices[graph->numVertices];
    topologicalSort(graph, sortedVertices);

    // 初始化最早开始时间和最晚开始时间
    for (int i = 0; i < graph->numVertices; i++) {
        earliestStart[i] = 0;
        latestStart[i] = INT_MAX;
    }

    // 计算每个节点的最早开始时间
    for (int i = 0; i < graph->numVertices; i++) {
        int currentVertex = sortedVertices[i];
        struct AdjListNode* currentNode = graph->adjLists[currentVertex].head;
        while (currentNode != NULL) {
            int destVertex = currentNode->dest;
            int weight = currentNode->weight;
            if (earliestStart[currentVertex] + weight > earliestStart[destVertex]) {
                earliestStart[destVertex] = earliestStart[currentVertex] + weight;
            }
            currentNode = currentNode->next;
        }
    }

    // 计算每个节点的最晚开始时间
    latestStart[graph->numVertices - 1] = earliestStart[graph->numVertices - 1];
    for (int i = graph->numVertices - 2; i >= 0; i--) {
        int currentVertex = sortedVertices[i];
        struct AdjListNode* currentNode = graph->adjLists[currentVertex].head;
        while (currentNode != NULL) {
            int destVertex = currentNode->dest;
            int weight = currentNode->weight;
            if (latestStart[destVertex] - weight < latestStart[currentVertex]) {
                latestStart[currentVertex] = latestStart[destVertex] - weight;
            }
            currentNode = currentNode->next;
        }
    }

    // 计算关键路径和总工期
    int criticalPathLength = 0;
    for (int i = 0; i < graph->numVertices; i++) {
        int currentVertex = sortedVertices[i];
        struct AdjListNode* currentNode = graph->adjLists[currentVertex].head;
        while (currentNode != NULL) {
            int destVertex = currentNode->dest;
            int weight = currentNode->weight;
            if (earliestStart[currentVertex] + weight == earliestStart[destVertex] &&
                latestStart[destVertex] - weight == latestStart[currentVertex]) {
                printf("%d -> %d\n", currentVertex, destVertex);
                criticalPathLength += weight;
            }
            currentNode = currentNode->next;
        }
    }

    return criticalPathLength;
}

在这个示例代码中，我们首先计算了拓扑排序序列，并初始化了最早开始时间和最晚开始时间。然后计算每个节点的最早开始时间和最晚开始时间，并计算关键路径和总工期。在计算关键路径时，我们遍历每条有向边，并检查其起始节点的最早开始时间和终止节点的最晚开始时间是否相等，如果相等，则说明这条边在关键路径上，我们将其输出，并累加其权值。

以上就是这道关于图的拓扑排序和关键路径算法的实验题目的一些实验提示，希望对你有所帮助。