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

本文主要是介绍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)算法的源代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/641045

相关文章

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

C# Where 泛型约束的实现

《C#Where泛型约束的实现》本文主要介绍了C#Where泛型约束的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录使用的对象约束分类where T : structwhere T : classwhere T : ne

C#实现将Excel表格转换为图片(JPG/ PNG)

《C#实现将Excel表格转换为图片(JPG/PNG)》Excel表格可能会因为不同设备或字体缺失等问题,导致格式错乱或数据显示异常,转换为图片后,能确保数据的排版等保持一致,下面我们看看如何使用C... 目录通过C# 转换Excel工作表到图片通过C# 转换指定单元格区域到图片知识扩展C# 将 Excel

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

Python如何自动生成环境依赖包requirements

《Python如何自动生成环境依赖包requirements》:本文主要介绍Python如何自动生成环境依赖包requirements问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录生成当前 python 环境 安装的所有依赖包1、命令2、常见问题只生成当前 项目 的所有依赖包1、

C#TextBox设置提示文本方式(SetHintText)

《C#TextBox设置提示文本方式(SetHintText)》:本文主要介绍C#TextBox设置提示文本方式(SetHintText),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑... 目录C#TextBox设置提示文本效果展示核心代码总结C#TextBox设置提示文本效果展示核心代

C#中DrawCurve的用法小结

《C#中DrawCurve的用法小结》本文主要介绍了C#中DrawCurve的用法小结,通常用于绘制一条平滑的曲线通过一系列给定的点,具有一定的参考价值,感兴趣的可以了解一下... 目录1. 如何使用 DrawCurve 方法(不带弯曲程度)2. 如何使用 DrawCurve 方法(带弯曲程度)3.使用Dr

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

MySQL中动态生成SQL语句去掉所有字段的空格的操作方法

《MySQL中动态生成SQL语句去掉所有字段的空格的操作方法》在数据库管理过程中,我们常常会遇到需要对表中字段进行清洗和整理的情况,本文将详细介绍如何在MySQL中动态生成SQL语句来去掉所有字段的空... 目录在mysql中动态生成SQL语句去掉所有字段的空格准备工作原理分析动态生成SQL语句在MySQL