数据结构课程设计/校园导游程序及通信线路设计 #2
本文章将根据编者的数据结构课程设计，讲解关于最短路径，最小生成树，关键路径等内容，涉及邻接矩阵和邻接表存储图结构； prim ** 算法；djstl迪杰斯特拉算法；关键路径AOE网；程序设计相关内容。
前景引入：
在之前的小结，我们成功进行了相关存储结构的搭建以及前两个问题的解决，现在让我们着手解决第三个问题：最小生成树。
最小生成树:
最小生成树，又称最小代价树，是边的权值之和最小的树。注意只有连通图有最小生成树。
因为我们是无向图，而且是特定的邻接表存储的图，使用kruskal算法不太方便，而prim算法实现比较简单，所以编者选择了prim算法来实现。
具体步骤如下：
- 初始化阶段：首先设置所有顶点的代价为无穷大（
no），并标记所有顶点未加入生成树。起始顶点的代价设为 0，并将其作为生成树的根节点。 - 选择最小代价的顶点：通过一个循环，选择代价最小的顶点并将其加入生成树。这个代价是指当前已加入生成树的顶点与未加入顶点之间的边权值。
- 更新代价：对于新加入生成树的顶点，遍历其所有邻接顶点，更新与生成树相连的未加入顶点的代价（即，更新
cost数组）。如果通过当前顶点连接某个未加入顶点的代价更小，就更新该顶点的代价并记录连接的父节点。 - 重复步骤：这个过程不断重复，直到所有顶点都被加入生成树。最终，
tree数组中保存了生成树的结构，即每个顶点的父节点，能够帮助我们恢复最小生成树的边。
普里姆算法的核心思想是利用贪心策略，每次选择最小的连接边，保证每一步的局部最优，从而最终得到全局最优解（最小生成树）。
以下是代码：
void communicationPlan(MGraph &G) { cout << "正在查询通信线路铺设方案..." << endl; int vmax = G.vexnum; int tree[vmax]; // 保存生成树 int cost[vmax]; bool flag[vmax] = {false}; // 标记顶点是否已加入生成树 int mincost, k; // 初始化cost数组 for (int i = 0; i < vmax; i++) { cost[i] = no; flag[i] = false; } // 这里不要把flag[0]设置为true,因为这个要在主循环中设置从而将其与其他节点连接 cost[0] = 0; // 起始顶点的代价为0 tree[0] = -1; // 根节点没有父节点 // 主循环，逐步扩展生成树 for (int i = 0; i < vmax; i++) { mincost = no; k = -1; // 用于存储代价最小的顶点下标 // 找到最小代价的顶点 for (int j = 0; j < vmax; j++) { if (!flag[j] && cost[j] < mincost) { mincost = cost[j]; k = j; // 记忆最小的边 } } // 如果没有找到合适的顶点，说明图不连通 if (k == -1) break; flag[k] = true; // 将顶点加入生成树 // 更新与生成树中新加入顶点相连的其他顶点的代价 Node* node = G.vArray[k].firstarc; while (node != NULL) { if (!flag[node->index] && node->distance < cost[node->index]) { cost[node->index] = node->distance; tree[node->index] = k; // 记录从哪个顶点连接 } node = node->next; } } // 打印最小生成树的结果 cout << "\n--- 最小生成树（通信线路方案） ---\n"; for (int i = 1; i < vmax; i++) { cout << "从 " << G.vArray[tree[i]].name << " 连接 " << G.vArray[i].name << " ，距离是： " << cost[i] << " 单位\n"; } cout << "\n----- 通信线路铺设方案已完成 -----\n";}