克鲁斯卡尔算法(C++)
目录
克鲁斯卡尔算法
编辑代码:
结果:
克鲁斯卡尔算法
克鲁斯卡尔算法是一种用于求解最小生成树的算法。最小生成树是指一棵包含了所有节点的连通图,并且边的权值之和最小。
克鲁斯卡尔算法的基本思想是,每次选择图中最小的边,如果这条边的加入不会形成环,则将它加入最小生成树中。重复以上过程,直到所有节点都被纳入最小生成树中。
具体实现时,可以使用并查集来判断加入一条边是否会形成环。在实现过程中,需要先对边按照权值进行排序,然后遍历每条边进行判断。

代码:
#include<iostream>
#include<algorithm>
using namespace std;
typedef int vertextype;
typedef struct node
{vertextype head;//边起始点vertextype tail;//边终点int w;//权值
}edge;
bool cmp(edge a, edge b)//权值小的排前面
{return a.w < b.w;
}
int main()
{edge e[100];int n, t, vexset[100];//顶点数、边数、连通分量cout << "输入顶点数和边数";cin >> n >> t;for (int i = 1; i <= n; i++)//初始化连通分量{vexset[i] = i;}cout << "输入边:" << endl;for (int i = 0; i < t; i++){int v1, v2, w;cin >> v1 >> v2 >> w;e[i].head = v1;e[i].tail = v2;e[i].w = w;}sort(e, e + t, cmp);int sum = 0;cout << "输出最小生成树:" << endl;for (int i = 0; i < t; i++){int v1, v2;v1 = e[i].head;v2 = e[i].tail;int vs1 = vexset[v1];//取v1连通分量int vs2 = vexset[v2];//取v2连通分量if (vs1 != vs2){sum += e[i].w;cout << v1 << " " << v2 << endl;for (int j = 1; j <= n; j++)//更新连通分量{if (vexset[j] == vs2)vexset[j] = vs1;}}}cout << "最小生成树权值:"<<sum;
}
结果:

相关文章:
克鲁斯卡尔算法(C++)
目录 克鲁斯卡尔算法 编辑代码: 结果: 克鲁斯卡尔算法 克鲁斯卡尔算法是一种用于求解最小生成树的算法。最小生成树是指一棵包含了所有节点的连通图,并且边的权值之和最小。 克鲁斯卡尔算法的基本思想是,每次选择图中最小的…...
【Shell脚本 4】测试用
#!/usr/bin/env bash # --------------------------------------------------------------------------------- # 控制台颜色 BLACK"\033[1;30m" RED"\033[1;31m" GREEN"\033[1;32m" YELLOW"\033[1;33m" BLUE"\033[1;34m"…...
DC电源模块对效率有什么要求?
BOSHIDA DC电源模块对效率有什么要求? DC电源模块是现代科技中非常重要的组成部分,它是将交流电转换为直流电的装置,可以提供稳定的电源给各种设备和系统使用。效率是DC电源模块的一个关键性能指标,直接影响着模块的整体性能和效…...
Linux在线安装MySQL8.0.24安装、MySQL数据备份和恢复
一、 Linux在线安装MySQL8.0.24 如果机器上已经有MySQL5.7版本需要先卸载 首先,需要停止MySQL服务。可以通过以下命令来停止服务: sudo systemctl stop mysqld接下来,我们需要卸载MySQL5.7。可以通过以下命令来卸载: sudo yum…...
【python】OpenCV—Rectangle, Circle, Selective Search(1.2)
文章目录 1 画框画圈1.1 画矩形框1.2 画圆 / 点1.3 椭圆 2 Selective Search3 Resize 1 画框画圈 1.1 画矩形框 # Copy the image img_rgb_copy img_rgb.copy()# Draw a rectangle cv2.rectangle(img_rgb_copy, pt1 (405, 90), pt2 (740, 510),color (255, 0, 0), thickne…...
MongoDB是一个NoSQL数据库,有着多种不同的命令和操作。以下是一些常见的MongoDB命令:
show dbs:列出所有数据库use db_name:切换到指定的数据库db.dropDatabase():删除当前数据库db.createCollection("collection_name"):创建集合db.collection_name.insert(document):向指定集合插入数据db.co…...
网络运维Day19
文章目录 环境准备数据备份为什么要备份什么是备份备份到哪里什么时候备份如何备份 完整备份物理备份逻辑备份测试恢复所有库 构建MySQL服务xtrabackup完全备份与恢复完全备份完全恢复增量备份增量恢复 总结 环境准备 IP地址采用自动分配,以自己的为准 可以将之前的…...
颜色标记txt和多根走线【Cadance进阶】
文章目录 前言颜色标记txt多根走线 前言 今天来介绍个基础操作中不常见的,但是非常实用的技巧。第一个是颜色标记,它是与text文件结合,根据text文件中的网络来染色标记的,致力于找出那些特定的走线,或者是查询出现问题…...
你是想被ChatGPT改变,还是改变软件开发的未来?丨IDCF
人工智能技术的发展,正在深刻地改变着我们的生活和工作方式。在软件工程领域,ChatGPT作为一种新兴的人工智能技术,正在逐渐地被应用到软件开发的各个环节中。那么,ChatGPT对每个人的影响是什么呢? 一、对软件开发人员…...
Homography详解在MVSNet中的应用
Homography(单应性变换)是计算机视觉中的一个重要概念,用于描述两个平面之间的透视关系。在图像处理和计算机视觉中,Homography通常表示两个平面之间的投影关系,这种关系可以通过一个3x3的矩阵来表示。 在数学上&…...
linux parted给磁盘分区
概述 通常我们用的比较多的分区工具是fdisk命令,但由于fdisk只支持MBR分区,MBR分区表最大支撑2T的磁盘,所以无法划分大于2T的分区。而parted工具可以划分单个分区大于2T的GPT格式的分区,也可以划分普通的MBR分区。 1.查看磁盘大小…...
大数据毕业设计选题推荐-机房信息大数据平台-Hadoop-Spark-Hive
✨作者主页:IT研究室✨ 个人简介:曾从事计算机专业培训教学,擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...
使用 PYTORCH 进行图像风格迁移
一、介绍 本教程介绍如何实现 由 Leon A. Gatys、Alexander S. Ecker 和 Matthias Bethge 开发的神经风格算法。神经风格或神经传输允许您拍摄图像并以新的艺术风格再现它。该算法采用三幅图像,即输入图像、内容图像和风格图像,并将输入更改为类似于内容…...
vscode使用flake8设置单行最长字符限制设置失败的问题
vscode使用flake8设置单行最长字符限制设置失败的问题 问题描述解决方案 问题描述 如图所示,使用flake8单行字数过长,就会有有红色底的波浪线 一般情况下很多教程都会让你在setting.json里面设置 但是我打开我的setting.json,发现我已经进…...
SAP KO22内部订单预算BAPI与BDC
KO22可以为内部订单预先维护预算,以便在后续成本实际产生时进行控制。 使用BAPI进行创建:KBPP_EXTERN_UPDATE_CO SAP note 625613中对该BAPI的使用方式有详细介绍,使用时可进行参考。 年度预算:e_gjahr传值、e_ges置空ÿ…...
K8S篇之实现利用Prometheus监控pod的实时数据指标
一、监控部署 1、将k8s集群中kube-state-metrics指标进行收集,服务进行部署 1.1 pod性能指标(k8s集群组件自动集成) k8s组件本身提供组件自身运行的监控指标以及容器相关的监控指标。通过cAdvisor 是一个开源的分析容器资源使用率和性能特性的…...
智能巡检软件怎么选?企业设备管理需要做什么?
在当今竞争激烈的企业运营环境中,巡检管理的重要性不言而喻。然而,许多企业在执行巡检任务时面临着诸多挑战,如员工执行不到位、缺乏有效的人员监管、漏检误检、安全隐患以及数据整理困难等问题。这些问题如果不能得到妥善解决,不…...
【python】Django——连接mysql数据库
笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ 【Django专栏】 Django——django简介、django安装、创建项目、快速上手 Django——templates模板、静态文件、django模板语法、请求和响应 Django——连接mysql数据库 Django——连接mysql数据库 连接MySQL数据库…...
北京君正客户应用案例:掌静脉3D人脸猫眼视屏智能锁
凯迪仕在今年4月发布了智能锁旗舰新品K70 Pro Max掌静脉3D人脸猫眼视屏智能锁,随即这款新品也成了行业热议的焦点。凯迪仕每次新品都力求突破精益求精,不仅追求科技感、高级感与品质感,而且赋予科技温度,带来人文化的关怀。K70 Pr…...
人工智能+游戏 会带来什么
“人工智能游戏” 写在前面 随着人类生活水平的日益提高,游戏正在为越来越多的人们带去欢乐。同时,作为21世纪新兴科学技术的人工智能,也正在研究人员的努力下不断向前突破。那么,这两列高速前进的“火车”能否接轨并行呢&#…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
R 语言科研绘图第 55 期 --- 网络图-聚类
在发表科研论文的过程中,科研绘图是必不可少的,一张好看的图形会是文章很大的加分项。 为了便于使用,本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中,获取方式: R 语言科研绘图模板 --- sciRplothttps://mp.…...
