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

简介: 【数据结构——图】最小生成树(头歌实践教学平台习题)目录任务描述相关知识测试说明我的通关代码:测试结果:【合集】任务描述本关任务:编写一个程序求图的最小生成树。相关知识为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767intA[MAXV][MAXV];Prim算法普里姆(Prim)算法是一种构造性算法,从候选边中挑

目录😋

任务描述

相关知识

带权无向图

建立邻接矩阵

Prim算法

1. 算法基本概念

2. 算法背景与目标

3. 算法具体步骤

4. 算法结束条件与结果

测试说明

通关代码

测试结果


任务描述

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

相关知识

为了完成本关任务,你需要掌握:

  1. 观察带权无向图
  2. 建立邻接矩阵
  3. Prim算法。
  • 带权无向图

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

image.gif 编辑 image.gif 编辑

  • 建立邻接矩阵

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

int A[MAXV][MAXV];
image.gif

注意: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
image.gif

预期输出:

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

开始你的任务吧,祝你成功!


通关代码

#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;
 }

image.gif


测试结果

image.gif

image.gif

目录
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
141 77
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
68 19
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
57 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
43 10
|
3月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
324 9
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
52 1
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
42 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
45 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
37 7
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
96 5