什么叫宣传型网站,合肥网站商城开发,手机免费注册,建设合同网上备案上哪个网站目录#x1f60b;
任务描述
相关知识
带权无向图
建立邻接矩阵
Prim算法
1. 算法基本概念
2. 算法背景与目标
3. 算法具体步骤
4. 算法结束条件与结果
测试说明
通关代码
测试结果 任务描述 本关任务#xff1a;编写一个程序求图的最小生成树。 相关知识 为了完成…目录
任务描述
相关知识
带权无向图
建立邻接矩阵
Prim算法
1. 算法基本概念
2. 算法背景与目标
3. 算法具体步骤
4. 算法结束条件与结果
测试说明
通关代码
测试结果 任务描述 本关任务编写一个程序求图的最小生成树。 相关知识 为了完成本关任务你需要掌握 观察带权无向图建立邻接矩阵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.husing 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; // 顶点uint v; // 顶点vint 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; // 将起始顶点加入Ufor (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和closestfor (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;} 测试结果
