【数据结构——图】最小生成树（头歌实践教学平台习题）【合集】

Rossy Yan

修改于 2024-12-26 10:29:27

14710

代码可运行

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

运行总次数：0

代码可运行

任务描述

本关任务：编写一个程序求图的最小生成树。

相关知识

为了完成本关任务，你需要掌握：

观察带权无向图
建立邻接矩阵
Prim算法。

带权无向图

针对带权无向图设计图的最小生成树，如下列图形。

建立邻接矩阵

上述带权无向图对应的二维数组，根据它建立下列邻接矩阵：

int A[MAXV][MAXV];

注意：INF表示无穷大，表示整数：32767

Prim算法

1. 算法基本概念普里姆（Prim）算法是图论中用于求解最小生成树的一种经典的构造性算法，其核心思想是通过逐步挑选权值最小的边来构建出整个图的最小生成树。 2. 算法背景与目标在一个连通无向图中（其中表示顶点集合，表示边集合，每条边都带有相应的权值），最小生成树是一棵包含图中所有顶点的无环连通子图，并且这棵子图所有边的权值之和是所有可能的生成树中最小的。Prim 算法就是为了高效地找出这样的最小生成树而设计的。 3. 算法具体步骤 第一步：初始化操作：

首先，任选图中的一个顶点，将其放入集合中，即。此时，集合表示已经被选入到正在构建的最小生成树中的顶点集合，而就是尚未被选入的顶点集合。
接着，把顶点到其他所有顶点（也就是中的顶点）的所有边都作为初始的候选边。这些候选边将成为后续挑选最小权值边的基础，它们都有可能最终被选入最小生成树当中。

第二步：迭代过程（重复次，其中是图中顶点的总数）：

步骤①：挑选最小权值边并更新顶点集合
- 从当前的候选边集合中，仔细挑选出权值最小的那一条边。这条边是连接集合中的顶点和中的顶点的边。设这条权值最小边在这一侧的顶点是。
- 然后，将顶点加入到集合中，这意味着已经被选入到正在构建的最小生成树里了。由于已经被选中，为了避免后续重复考虑一些不合适的边以及保证生成树无环等性质，需要把和顶点关联的其他边（也就是一端是，另一端在中的边）从候选边集合中删除掉。
步骤②：修改候选边集合
- 接下来，需要考察当前中的每一个顶点，去更新与之相关的候选边情况。对于每一个，如果存在边，并且这条边的权值小于原来和关联的候选边的权值（也就是之前被视为连接到中顶点的最小权值边），那么就用边取代原来那条候选边，作为新的连接到中顶点的候选边。通过这样不断地更新候选边集合，能保证在每一轮迭代中，候选边始终是连接已选顶点集合和未选顶点集合的当前最优选择，从而逐步构建出最小生成树。

4. 算法结束条件与结果当上述迭代过程重复了次之后，此时集合中已经包含了图的所有个顶点，而挑选出来的边就构成了图的一棵最小生成树。整个过程通过不断挑选局部最优（权值最小）的边，最终实现了全局最优（生成树边权值总和最小）的目标。 例如：对于一个简单的连通无向图，有 5 个顶点、、、、，各边有权值，若一开始选择顶点作为放入中，然后按照 Prim 算法的步骤逐步挑选边、更新候选边以及加入新顶点，经过 4 次迭代后，就能得到该图的最小生成树，且这棵最小生成树的边权值总和是所有可能生成树中最小的。

测试说明

平台会对你编写的代码进行测试：

测试输入：(先输入图的顶点数和边数，再输入图的邻接矩阵。)

6 10 0 5 8 7 32767 3 5 0 4 32767 32767 32767 8 4 0 5 32767 9 7 32767 5 0 5 6 32767 32767 32767 5 0 1 3 32767 9 6 1 0

预期输出：

Prim算法求解结果: 边(0,5)权为:3 边(5,4)权为:1 边(0,1)权为:5. 边(1,2)权为:4 边(4,3)权为:5

开始你的任务吧，祝你成功！

通关代码

 #include <bits/stdc++.h>
 using namespace std;
 //图的存储结构
 #define INF 32767 //定义∞
 #define MAXV 100 //最大顶点个数
 typedef char InfoType;
 
 // 邻接矩阵表示的图
 typedef struct {
   int edges[MAXV][MAXV]; // 邻接矩阵
   int n, e;              // 顶点数和边数
 } MGraph;
 
 // 边的结构体
 typedef struct {
   int u; // 顶点u
   int v; // 顶点v
   int w; // 边(u, v)的权值
 } Edge;
 
 // 初始化图
 void InitGraph(MGraph &g) {
   for (int i = 0; i < MAXV; i++) {
     for (int j = 0; j < MAXV; j++) {
       g.edges[i][j] = INF;
     }
   }
 }
 
 // Prim算法
 void Prim(MGraph g, int start) {
   int lowcost[MAXV]; // 存储从U到V-U的边中最小权值
   int closest[MAXV]; // 存储V-U中与U最接近的顶点
   bool u[MAXV];      // 标记顶点是否已在U中
 
   // 初始化
   for (int i = 0; i < g.n; i++) {
     lowcost[i] = g.edges[start][i];
     closest[i] = start;
     u[i] = false;
   }
 
   u[start] = true;                // 将起始顶点加入U
   for (int i = 1; i < g.n; i++) { // 需要加入n-1个顶点
     int min = INF;
     int k = -1;
     // 找到最小的边
     for (int j = 0; j < g.n; j++) {
       if (!u[j] && lowcost[j] < min) {
         min = lowcost[j];
         k = j;
       }
     }
     // 输出最小生成树的边
     cout << "边(" << closest[k] << "," << k << ")权为:" << min << endl;
     u[k] = true; // 将顶点k加入U
                  // 更新lowcost和closest
     for (int j = 0; j < g.n; j++) {
       if (!u[j] && g.edges[k][j] < lowcost[j]) {
         lowcost[j] = g.edges[k][j];
         closest[j] = k;
       }
     }
   }
 }
 
 int main() {
   MGraph g;
   int n, e;
   cin >> n >> e; // 输入顶点数和边数
   g.n = n;
   g.e = e;
   InitGraph(g);
   // 输入邻接矩阵
   for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
       cin >> g.edges[i][j];
     }
   }
   // 调用Prim算法
   cout << "Prim算法求解结果:" << endl;
   Prim(g, 0); // 从顶点0开始
   return 0;
 }