服务器如何搭建网站_网页设计尺寸早起可视尺寸_抖音信息流广告怎么投放_搜索引擎提交入口网址

本文章将根据编者的数据结构课程设计，讲解关于最短路径，最小生成树，关键路径等内容，涉及邻接矩阵和邻接表存储图结构；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数组的所有元素初始化为nostack<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();  // 获取栈顶元素，即当前处理的顶点uS.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的入度减1if (G.indegree[v] == 0) {  // 如果v的入度变为0，说明可以处理vS.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];  // 获取逆拓扑排序中的顶点uNode* 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就好了，其他地方应该是不用操作的。