数据结构课程设计/校园导游程序及通信线路设计 #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就好了，其他地方应该是不用操作的。