数据结构课程设计/校园导游程序及通信线路设计 #2

本文章将根据编者的数据结构课程设计，讲解关于最短路径，最小生成树，关键路径等内容，涉及邻接矩阵和邻接表存储图结构；prim算法；djstl迪杰斯特拉算法；关键路径AOE网；程序设计相关内容。

前景引入：

在之前的小结，我们成功进行了相关存储结构的搭建以及前两个问题的解决，现在让我们着手解决第三个问题：最小生成树。

最小生成树:

最小生成树，又称最小代价树，是边的权值之和最小的树。注意只有连通图有最小生成树。

因为我们是无向图，而且是特定的邻接表存储的图，使用kruskal算法不太方便，而prim算法实现比较简单，所以编者选择了prim算法来实现。

具体步骤如下：

1. 初始化阶段：首先设置所有顶点的代价为无穷大（no），并标记所有顶点未加入生成树。起始顶点的代价设为 0，并将其作为生成树的根节点。

2. 选择最小代价的顶点：通过一个循环，选择代价最小的顶点并将其加入生成树。这个代价是指当前已加入生成树的顶点与未加入顶点之间的边权值。

3. 更新代价：对于新加入生成树的顶点，遍历其所有邻接顶点，更新与生成树相连的未加入顶点的代价（即，更新 cost 数组）。如果通过当前顶点连接某个未加入顶点的代价更小，就更新该顶点的代价并记录连接的父节点。

4. 重复步骤：这个过程不断重复，直到所有顶点都被加入生成树。最终，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";
}