C#,最小生成树(MST)克鲁斯卡尔(Kruskal)算法的源代码

一、Kruskal算法简史
克鲁斯卡尔(Kruskal)算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是,Kruskal算法在图中存在相同权值的边时也有效。

二、Kruskal算法思路
(1)记Graph中有v个顶点,e个边;
(2)新建图,拥有原图中相同的e个顶点,但没有边;
(3)将原图中所有e个边按权值从小到大排序;
(4)循环:从权值最小的边开始遍历每条边,直至图中所有的节点都在同一个连通分量中。
如果这条边连接的两个节点于图中不在同一个连通分量中,添加这条边到图中。如此反复。
三、Kruskal算法的源代码
核心代码:
using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public class Subset{public int Parent { get; set; } = 0;public int Rank { get; set; } = 0;}/// <summary>/// 最小生成树 Kruskal 算法/// </summary>public static class MST_Kruskal_Algorithm{private static int Find(Subset[] subsets, int i){if (subsets[i].Parent != i){subsets[i].Parent = Find(subsets, subsets[i].Parent);}return subsets[i].Parent;}private static void Union(Subset[] subsets, int x, int y){int xroot = Find(subsets, x);int yroot = Find(subsets, y);if (subsets[xroot].Rank < subsets[yroot].Rank){subsets[xroot].Parent = yroot;}else if (subsets[xroot].Rank > subsets[yroot].Rank){subsets[yroot].Parent = xroot;}else{subsets[yroot].Parent = xroot;subsets[xroot].Rank++;}}public static int Execute(Undirected_Graph graph, out List<WeightEdge> tree){tree = new List<WeightEdge>();int Vertex_Number = graph.Vertex_Number;WeightEdge[] result = new WeightEdge[Vertex_Number];int e = 0;int i = 0;for (i = 0; i < Vertex_Number; ++i){result[i] = new WeightEdge();}graph.EdgeArray.Sort(delegate(WeightEdge a, WeightEdge b) { return a.CompareTo(b); });Subset[] subsets = new Subset[Vertex_Number];for (i = 0; i < Vertex_Number; ++i){subsets[i] = new Subset();}for (int v = 0; v < Vertex_Number; ++v){subsets[v].Parent = v;subsets[v].Rank = 0;}i = 0;while (e < (Vertex_Number - 1)){WeightEdge next_edge = graph.EdgeArray[i++];int x = Find(subsets, next_edge.Start);int y = Find(subsets, next_edge.End);if (x != y){result[e++] = next_edge;Union(subsets, x, y);}}int minimumCost = 0;for (i = 0; i < e; ++i){tree.Add(new WeightEdge(result[i].Start,result[i].End, result[i].Weight));minimumCost += result[i].Weight;}return minimumCost;}}
}
——————————————————————
POWER BY 315SOFT.COM &
TRUFFER.CN
相关文章:
C#,最小生成树(MST)克鲁斯卡尔(Kruskal)算法的源代码
一、Kruskal算法简史 克鲁斯卡尔(Kruskal)算法是一种用来寻找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪婪算法的应用。和Boruvka算法不同的地方是,Kruska…...
Oracle篇—参数文件在11gRAC或12cRAC的启动位置介绍
☘️博主介绍☘️: ✨又是一天没白过,我是奈斯,DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、Linux,也在积极的扩展IT方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注❣…...
scrapy pipelines
1.时间的处理 获取当前时间的字符串 # 创建一个datetime对象并设置为当前时间,该时间少8小时 dt datetime.datetime.now() # 将datetime转换为本地时区 local_tz pytz.timezone(Asia/Shanghai) local_dt local_tz.localize(dt) # 将datetime对象格式化为ISO 86…...
element-ui 打包流程源码解析——babel 相关
目录 1,babel-cli2,babel-core3,.babelrc3.1,presets3.2,plugins其他相关 该文章是为了更好的理解:element-ui 打包流程源码解析(上) 第2.5节 npm run build:utils 打包命令 "…...
听神经瘤的听力学表现
听神经瘤的听力学诊断 听神经瘤的听力学表型多样,听力正常者不能排除听神经瘤;听力损失程度不能预判肿瘤大小;纯音测听与言语识别率不一致应警惕蜗后病变;听性脑干诱发电位诊断听神经瘤敏感度随肿瘤增大而增加。 一.纯…...
C#用DateTime.Now静态属性返回日期的星期信息
目录 一、使用的方法 1.Now属性 2.ToString方法 二、示例 使用DateTime结构的Now静态属性,可以方便地获取系统日期信息。调用时间对象的ToString方法,在该方法的参数中添加适当的格式化字符串,将返回日期的星期信息。 一、使用的方法 1…...
ARMv8-AArch64 的异常处理模型详解之异常类型 Exception types
异常类型详解 Exception types 一, 什么是异常二,同步异常(synchronous exceptions)2.1 无效的指令和陷阱异常(Invalid instructions and trap exceptions)2.2 内存访问产生的异常2.3 产生异常的指令2.4 调…...
Linux操作系统概念
绪论: “心灵纯洁的人,生活充满甜蜜和喜悦。——列夫托尔斯泰”,本章的主要内容是介绍了硬件的组成结构冯诺依曼体系结构以及操作系统的概念和操作系统的作用,本章的内容主要是理论他起到承上启下的作用只有理解了操作系统的运行…...
Speech | 人工智能中关于语音务必需要了解的基础知识(信号处理)及代码
语音是指人们讲话时发出的话语,是一种人们进行信息交流的声音,是由一连串的音组成语言的声音,我们可以理解为语音(speech)声音(acoustic)语言(language)。 目录 0.声音的基本属性 0.1.音高(pitch) 0.2.音量(Volume) 0.3.音色(Timbre) 0…...
c# 单例模式实现
方式一: 在C#中,可以使用单例模式来确保一个类只有一个实例,并提供一个全局访问点。 public class Singleton {private static Singleton instance;private static readonly object lockObject new object();private Singleton(){// 私有构…...
万字长文详解Java线程池面试题
王有志,一个分享硬核 Java 技术的互金摸鱼侠 加入 Java 人的提桶跑路群:共同富裕的Java人 今天是《面霸的自我修养》第 6 篇文章,我们一起来看看面试中会问到哪些关于线程池的问题吧。数据来源: 大部分来自于各机构(J…...
【jQuery入门】链式编程、修改css、类操作和className的区别
文章目录 前言一、链式编程二、修改css2.1 获取css的值2.2 设置单个css属性2.3 设置类样式添加类移除类切换类 三、类操作与className的区别总结 前言 jQuery是一个流行的JavaScript库,广泛用于简化DOM操作和处理事件。在jQuery中,链式编程是一种强大的…...
使用的uview 微信高版本 头像昵称填写能力
<template><view><button class"cu-btn block bg-blue margin-tb-sm lg" tap"wxGetUserInfo">一键登录</button><view><!-- 提示窗示例 --><u-popup :show"show" background-color"#fff">&…...
Hadoop3完全分布式搭建
一、第一台的操作搭建 修改主机名 使用hostnamectl set-hostname 修改当前主机名 关闭防火墙和SELlinux 1,使用 systemctl stop firewalld systemctl disable firewalld 关闭防火墙 2,使用 vim /etc/selinux/config 修改为 SELINUXdisabled 使用N…...
中断——外部中断EXIT
前期疑问:中断可以分成外部中断和内部中断吗 文章目录 前言一、中断知识二、中断编程三、EXIT外部中断/事件控制器 3.1 中断事件线3.2 EXTI初始化结构体详解 四、软件设计 4.1 编程要点 五、代码回顾实现六、补充中断知识总结 前言 野火中断章节有这样一句话 【F…...
Kafka-服务端-副本机制
Kafka从0.8版本开始引入副本(Replica)的机制,其目的是为了增加Kafka集群的高可用性。 Kafka实现副本机制之后,每个分区可以有多个副本,并且会从其副本集合(Assigned Replica,AR)中选出一个副本作为Leader副本,所有的读写请求都由…...
银行数据仓库体系实践(4)--数据抽取和加载
1、ETL和ELT ETL是Extract、Transfrom、Load即抽取、转换、加载三个英文单词首字母的集合: E:抽取,从源系统(Souce)获取数据; T:转换,将源系统获取的数据进行处理加工,比如数据格式转化、数据精…...
云计算入门——Linux 命令行入门
云计算入门——Linux 命令行入门 前些天发现了一个人工智能学习网站,通俗易懂,风趣幽默,最重要的屌图甚多,忍不住分享一下给大家。点击跳转到网站。 介绍 如今,我们许多人都熟悉计算机(台式机和笔记本电…...
自然语言处理(NLP)的发展
自然语言处理的发展 随着深度学习和大数据技术的进步,自然语言处理取得了显著的进步。人们正在研究如何使计算机更好地理解和生成人类语言,以及如何应用NLP技术改善搜索引擎、语音助手、机器翻译等领域。 方向一:技术进步 自然语言处理&…...
让uniapp小程序支持多色图标icon:iconfont-tools-cli
前景: uniapp开发小程序项目时,对于iconfont多色图标无法直接支持;若将多色icon下载引入项目则必须关注包体,若将图标放在oss或者哪里管理,加载又是一个问题,因此大多采用iconfont-tools工具,但…...
Aurix/Tricore实验解析:从链接脚本到汇编指令的Trap向量表构建
1. 理解Trap机制与向量表基础 在Aurix/Tricore架构中,Trap(陷阱)是处理器响应异常事件的硬件机制,相当于汽车的安全气囊——平时看不见,但遇到碰撞时会立即触发保护。与中断不同,Trap是同步触发的ÿ…...
构建智能体的专业技能树 - Agent Skills生态全析(中篇)
一、概述 这篇文章我们将围绕Skills、Tools、MCP、Subagents 四个组件有什么区别、Anthropic 官方做好了哪些现成 Skills、如何从零创建一个自定义 Skill 的完整流程 这些四个方面来进行讲解。 二、智能体生态系统概览 在 Anthropic 构建的智能体生态中,多种技术组件…...
快速部署MinerU镜像:开箱即用的PDF提取方案,告别繁琐配置
快速部署MinerU镜像:开箱即用的PDF提取方案,告别繁琐配置 1. 引言:为什么你需要一个“开箱即用”的PDF提取工具? 如果你曾经尝试过从一份复杂的PDF文档里提取文字、表格和公式,你大概率经历过这样的痛苦:…...
如何用Steam Achievement Manager掌控游戏成就?解锁7大实用技巧
如何用Steam Achievement Manager掌控游戏成就?解锁7大实用技巧 【免费下载链接】SteamAchievementManager A manager for game achievements in Steam. 项目地址: https://gitcode.com/gh_mirrors/st/SteamAchievementManager 在游戏世界中,成就…...
告别天价桥接芯片!用高云GW5AT-LV15MG132 FPGA搞定MIPI C-PHY摄像头测试盒
国产FPGA革新摄像头测试方案:高云GW5AT-LV15MG132的MIPI C-PHY实战解析 在摄像头模组生产线上,测试环节的成本与效率直接关系到企业竞争力。传统测试方案依赖进口FPGA搭配昂贵桥接芯片,不仅物料清单(BOM)成本居高不下…...
英雄联盟自动化助手:提升游戏效率的全方位解决方案
英雄联盟自动化助手:提升游戏效率的全方位解决方案 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League Akari作为一…...
DeepSeek-OCR-2效果展示:OCR结果直接生成可编辑Word/PDF双格式
DeepSeek-OCR-2效果展示:OCR结果直接生成可编辑Word/PDF双格式 本文展示DeepSeek-OCR-2模型的强大OCR能力,重点演示如何将扫描文档直接转换为可编辑的Word和PDF格式,让文档数字化变得简单高效。 1. 核心能力概览 DeepSeek-OCR-2是2026年1月发…...
IPXWrapper终极指南:三步让Windows 11完美运行经典游戏联机对战
IPXWrapper终极指南:三步让Windows 11完美运行经典游戏联机对战 【免费下载链接】ipxwrapper 项目地址: https://gitcode.com/gh_mirrors/ip/ipxwrapper 还在为Windows 11无法运行《红色警戒2》、《星际争霸》等经典游戏而烦恼吗?IPXWrapper正是…...
3个突破性技术,让抖音无水印视频下载效率提升200%
3个突破性技术,让抖音无水印视频下载效率提升200% 【免费下载链接】douyin-downloader A practical Douyin downloader for both single-item and profile batch downloads, with progress display, retries, SQLite deduplication, and browser fallback support. …...
Qwen3-0.6B-FP8应用场景:开发者测试LLM应用前端UI兼容性的沙盒环境
Qwen3-0.6B-FP8应用场景:开发者测试LLM应用前端UI兼容性的沙盒环境 1. 引言:为什么需要一个轻量级的“测试沙盒”? 如果你正在开发一个基于大语言模型的应用,比如一个智能客服系统、一个文档助手,或者一个创意写作工…...
