数据结构课程设计/校园导游程序及通信线路设计 #3
本文章将根据编者的数据结构课程设计，讲解关于最短路径，最小生成树，关键路径等内容，涉及邻接 矩阵 ** 和邻接表存储图结构； prim ** 算法；djstl迪杰斯特拉算法；关键路径AOE网；程序设计相关内容。
前景引入：
在之前的小结，我们成功进行了相关存储结构的搭建以及前三个问题的解决，现在我们进行最后一个问题，也是最复杂的：关键路径的输出。
由于关键路径要求是有向图，我们便根据要求将之前用来内置无向图的二维数组进行修改
// 有向图 int edge_goto[13][13] = { {no, 5, no, no, no, no, no, no, no, no, no, no, no}, {no, no, 3, 4, no, no, no, no, no, no, no, no, no}, {no, no, no, no, 5, no, no, no, no, no, no, no, no}, {no, no, no, no, no, 7, no, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, 3, no, no, no, no, no}, {no, no, no, no, no, no, no, no, 4, no, no, no, no}, {no, no, no, no, no, no, no, no, no, 2, no, no, no}, {no, no, no, no, no, no, no, no, no, no, 6, 7, no}, {no, no, no, no, no, no, no, no, no, no, no, 2, no}, {no, no, no, no, no, no, no, no, no, no, no, no, 5}, {no, no, no, no, no, no, no, no, no, no, no, no, 7}, {no, no, no, no, no, no, no, no, no, no, no, no, no}};// 用于选择的数组指针 int (*selectedArray)[13];
在存储结构定义那一节我们已经进行了置入，现在不作赘述。
将switch中的语句做如下修改:
case 4: MGraph G1; initG(G1, 1); // 启用有向图 if (!constructionSchedule(G1)) { cout << "拓扑排序失败！" << endl; } system("pause"); break;
为了方便直接初始化一个新的有向图，然后是拓扑排序函数。
详细教学可以看我的这篇文章：AOE网/关键路径-CSDN博客
这里直接将代码给大家，结合注释比较清晰
AOE网
bool constructionSchedule(MGraph &G) { system("cls"); cout << "正在查询北门建设工期..." << endl; int *ve, *vl; // 定义两个指针，ve表示各顶点的最早发生时间，vl表示最晚发生时间 ve = new int[G.vexnum]; // 动态分配内存，ve数组用于保存各顶点的最早发生时间 vl = new int[G.vexnum]; // 动态分配内存，vl数组用于保存各顶点的最晚发生时间 fill(ve, ve + G.vexnum, 0); // 将ve数组的所有元素初始化为0（表示最早发生时间初始为0） fill(vl, vl + G.vexnum, no); // 将vl数组的所有元素初始化为no stack<int> S; // 使用栈来辅助拓扑排序 vector<int> print(G.vexnum, -1); // 用一个数组print记录拓扑排序后的顶点顺序，初始化为-1表示未排序 int count = 0; // 计数器，用于记录拓扑排序的顶点数 // 初始化栈，将所有入度为0的顶点入栈 for (int i = 0; i < G.vexnum; i++) { if (G.indegree[i] == 0) { // 如果顶点i的入度为0，说明它没有前驱，可以先处理 S.push(i); // 入栈 } } // 开始拓扑排序 while (!S.empty()) { // 当栈不为空时，继续拓扑排序 int u = S.top(); // 获取栈顶元素，即当前处理的顶点u S.pop(); // 弹出栈顶元素 print[count++] = u; // 将顶点u加入拓扑排序的结果中，并更新计数器 // 遍历与顶点u相邻的所有顶点 Node* p = G.vArray[u].firstarc; // 获取顶点u的邻接表中的第一个边 while (p != NULL) { // 遍历所有与u相邻的顶点 int v = p->index; // 获取与u相邻的顶点v // 更新v的入度 G.indegree[v]--; // 将顶点v的入度减1 if (G.indegree[v] == 0) { // 如果v的入度变为0，说明可以处理v S.push(v); // 将v入栈 } // 更新最早发生时间 ve[v] = max(ve[v], ve[u] + p->distance); // 更新v的最早发生时间，ve[v] = max(当前的ve[v], u的最早发生时间 + u到v的边的权重) p = p->next; // 移动到下一个邻接点 } } // 判断是否完成拓扑排序，如果count不等于图的顶点数，说明存在环 if (count != G.vexnum) { cout << "图中存在环，无法进行拓扑排序！" << endl; // 输出错误信息，图中存在环 return false; // 返回false，表示无法进行拓扑排序 } // 输出拓扑排序结果 cout << "拓扑排序结果：\n"; for (int i = 0; i < G.vexnum; i++) { if (print[i] != -1) { // 确保输出的顶点是有效的 cout << G.vArray[print[i]].nickname << " "; // 输出顶点的昵称 } } cout << endl; // 输出各顶点的最早发生时间 cout << "各顶点的最早发生时间 (ve):\n"; for (int i = 0; i < G.vexnum; i++) { cout << G.vArray[i].nickname << ": " << ve[i] << endl; // 输出每个顶点的最早发生时间 } // 计算各顶点的最晚发生时间 // 初始化最晚发生时间vl为图中所有顶点的最早发生时间最大值 for (int i = 0; i < G.vexnum; i++) { vl[i] = ve[G.vexnum - 1]; // 将最晚发生时间初始化为最后一个顶点的最早发生时间 } // 进行逆拓扑排序来计算最晚发生时间 for (int i = G.vexnum - 1; i >= 0; i--) { int u = print[i]; // 获取逆拓扑排序中的顶点u Node* p = G.vArray[u].firstarc; // 获取顶点u的邻接表中的第一个边 while (p != NULL) { // 遍历u的所有邻接点 int v = p->index; // 获取与u相邻的顶点v // 更新v的最晚发生时间 vl[u] = min(vl[u], vl[v] - p->distance); // 更新最晚发生时间vl[u]，取最小值 p = p->next; // 移动到下一个邻接点 } } // 输出各顶点的最晚发生时间 cout << "各顶点的最晚发生时间 (vl):\n"; for (int i = 0; i < G.vexnum; i++) { cout << G.vArray[i].nickname << ": " << vl[i] << endl; // 输出每个顶点的最晚发生时间 } // 输出关键路径 cout << "关键路径：\n"; for (int i = 0; i < G.vexnum; i++) { Node* p = G.vArray[i].firstarc; // 获取顶点i的邻接表中的第一个边 while (p != NULL) { // 遍历与i相邻的所有顶点 int v = p->index; // 获取与i相邻的顶点v // 判断i->v是否在关键路径上：如果ve[i] == vl[v] - p->distance，说明这条边是关键路径的一部分 if (ve[i] == vl[v] - p->distance) { cout << G.vArray[i].name << "->" << G.vArray[v].name << " "; // 输出关键路径的边 } p = p->next; // 移动到下一个邻接点 } } return true; // 返回true，表示成功完成了建设工期的计算}
以下是结果：
ps:这里实际上是北门到南门，由于初始化图的时候没注意到要求，所以就这样了。
改也好改，将有向图调转方向（取下三角）然后初始化时将南门的入度改为0就好了，其他地方应该是不用操作的。