技术图文：如何利用C# 实现 Prim 最小生成树算法？
背景
我们上一篇图文介绍了 如何利用 C# 实现 Kruskal 最小生成树算法？，Kruskal 算法通过寻找边最优的方式来构造最小生成树，本篇图文介绍如何利用 C# 实现 Prim 最小生成树算法，Prim 算法通过寻找顶点最优的方式来构造最小生成树。
在继续介绍 Prim 算法之前，我整理了以前发布的有关数据结构与算法的图文，建个索引以方便大家的复习啊。
线性结构
- 如何利用“栈”解决“出轨”问题？
- 如何利用“队列”解决“窗口混乱”问题？
- 字符串的模式匹配算法
树形结构
- 如何利用C#实现Huffman编码？
排序相关
- 8大排序算法之：直接插入排序
- 8大排序算法之：希尔插入排序
- 8大排序算法之：直接选择排序
- 8大排序算法之：堆选择排序
- 8大排序算法之：冒泡排序
- 8大排序算法之：快速交换排序
- 8大排序算法之：并归排序
- 8大排序算法之：桶排序
搜索相关
- 8大搜索算法之：顺序搜索
- 8大搜索算法之：二分搜索
- 8大搜索算法之：插补搜索
- 8大搜索算法之：二叉搜索树（上）
- 8大搜索算法之：二叉搜索树（中）
- 8大搜索算法之：二叉搜索树（下）
- 8大搜索算法之：AVL树（上）
- 8大搜索算法之：AVL树（中）
- 8大搜索算法之：AVL树（下）
- 8大搜索算法之：红黑树（上）
- 8大搜索算法之：红黑树（中）
- 8大搜索算法之：红黑树（下）
LeetCode 实战
- LeetCode实战：旋转链表
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：两两交换链表中的节点
技术分析
Prim 算法：
例子：
该例子演示了一个含有6个结点，10条边的联通网，通过 Prim 算法从 V0 点开始逐步演化为含有6个结点，5条边的连通子网的过程，即构造最小生成树的过程。
代码实现
我们利用邻接表的方式来存储图的结构。有关于边表 EdgeNode、顶点表 VertexNode 和图 AdGraph 的结构，参见 如何利用 C# 实现 Kruskal 最小生成树算法？ 中的 Step1、Step2 和 Step3。
上面例子，在内存中的邻接表结构为：
最小生成树的节点结构 SpanTreeNode，参见 如何利用 C# 实现 Kruskal 最小生成树算法？ 中的 Step4。
有了以上的基础，我们就可以写 Prim 算法了。
public SpanTreeNode[] MiniSpanTree(string vName)
{int i = GetIndex(vName);if (i == -1)return null;SpanTreeNode[] spanTree = new SpanTreeNode[VertexCount];//首先加入根节点spanTree[0] = new SpanTreeNode(_vertexList[i].VertexName,"NULL", 0.0);//U中结点到各结点最小权值那个结点在VertexList中的索引号int[] vertexIndex = new int[VertexCount];//U中结点到各个结点的最小权值double[] lowCost = new double[VertexCount];for (int j = 0; j < VertexCount; j++){lowCost[j] = double.MaxValue;vertexIndex[j] = i;}EdgeNode p1 = _vertexList[i].FirstNode;while (p1 != null){lowCost[p1.Index] = p1.Weight;p1 = p1.Next;}vertexIndex[i] = -1;for (int count = 1; count < VertexCount; count++){double min = double.MaxValue;int v = i;for (int k = 0; k < VertexCount; k++){if (vertexIndex[k] != -1 && lowCost[k] < min){min = lowCost[k];v = k;}}spanTree[count] = new SpanTreeNode(_vertexList[v].VertexName,_vertexList[vertexIndex[v]].VertexName, min);vertexIndex[v] = -1;EdgeNode p2 = _vertexList[v].FirstNode;while (p2 != null){if (vertexIndex[p2.Index] != -1 &&p2.Weight < lowCost[p2.Index]){lowCost[p2.Index] = p2.Weight;vertexIndex[p2.Index] = v;}p2 = p2.Next;}}return spanTree;
}
总结
到此为止代码部分就全部介绍完了，我们来看一下上面例子的应用。
利用邻接表存储图的结构。
static AdGraph CreateGraph()
{AdGraph result = new AdGraph(6);result[0] = "V0";result[1] = "V1";result[2] = "V2";result[3] = "V3";result[4] = "V4";result[5] = "V5";result.AddEdge("V0", "V1", 6);result.AddEdge("V0", "V2", 1);result.AddEdge("V0", "V3", 5);result.AddEdge("V1", "V0", 6);result.AddEdge("V1", "V2", 5);result.AddEdge("V1", "V4", 3);result.AddEdge("V2", "V0", 1);result.AddEdge("V2", "V1", 5);result.AddEdge("V2", "V3", 7);result.AddEdge("V2", "V4", 5);result.AddEdge("V2", "V5", 4);result.AddEdge("V3", "V0", 5);result.AddEdge("V3", "V2", 7);result.AddEdge("V3", "V5", 2);result.AddEdge("V4", "V1", 3);result.AddEdge("V4", "V2", 5);result.AddEdge("V4", "V5", 6);result.AddEdge("V5", "V2", 4);result.AddEdge("V5", "V3", 2);result.AddEdge("V5", "V4", 6);return result;
}
从 V2 点开始构建最小生成树。
static void Main(string[] args)
{AdGraph alg = CreateGraph();SpanTreeNode[] tree = alg.MiniSpanTree("V2");double sum = 0;for (int i = 0; i < tree.Length; i++){string str = "(" + tree[i].ParentName + ","+ tree[i].SelfName + ") Weight:"+ tree[i].Weight;Console.WriteLine(str);sum += tree[i].Weight;}Console.WriteLine(sum);
}
结果如下：
我们再通过一个例子来演示如何应用：
上面是一幅纽约市附近的地图，对应的数据存储在 graph.txt 文件中。
读入该文件，构造好 AdGraph 结构后，调用我们写好的 Prim 算法，得到的结果如下：
是不是很有趣，今天就到这里吧！马上要放假了，我们的招新活动也即将开启，希望大家关注呦！
See You！
相关图文：
- 如何利用 C# 实现 K 最邻近算法？
- 如何利用 C# 实现 K-D Tree 结构？
- 如何利用 C# + KDTree 实现 K 最邻近算法？
- 如何利用 C# 对神经网络模型进行抽象？
- 如何利用 C# 实现神经网络的感知器模型？
- 如何利用 C# 实现 Delta 学习规则？
- 如何利用 C# 爬取带 Token 验证的网站数据？
- 如何利用 C# 向 Access 数据库插入大量数据？
- 如何利用 C# 开发「桌面版百度翻译」软件！
- 如何利用 C# 开发「股票数据分析软件」（上）
- 如何利用 C# 开发「股票数据分析软件」（中）
- 如何利用 C# 开发「股票数据分析软件」（下）
- 如何利用 C# 爬取「财报说」中的股票数据？
- 如何利用 C# 爬取 One 持有者返利数据！
- 如何利用 C# 爬取Gate.io交易所的公告！
- 如何利用 C# 爬取BigOne交易所的公告！
- 如何利用 C# 爬取 ONE 的交易数据？
- 如何利用 C# 爬取「猫眼电影：热映口碑榜」及对应影片信息！
- 如何利用 C# 爬取「猫眼电影专业版：票房」数据！
- 如何利用 C# 爬取「猫眼电影：最受期待榜」及对应影片信息！
- 如何利用 C# 爬取「猫眼电影：国内票房榜」及对应影片信息！
- 如何利用 C# + Python 破解猫眼电影的反爬虫机制？
- 如何利用BigOne的API制作自动化交易系统 – 身份验证
- 如何利用BigOne的API制作自动化交易系统 – 获取账户资产
- 如何利用BigOne的API制作自动化交易系统 – 订单系统
相关文章：
去除iphone图标的半弧高亮效果
只需要在info.plist里面添加一条记录UIPrerenderedIcon 新版的XCODE 会自动识别为Icon already includes gloss effects 打上勾就OK了 如果没有识别的右边栏写上YES就可以。转载于:https://www.cnblogs.com/jiewong/archive/2011/01/14/1935718.html
【短视频SDK - 参数解析】对焦模式、裁剪模式、视频质量、分辨率、视频比例、帧率、关键帧间隔等参数解析...
1.参数简析 参数名称简介影响裁剪模式分为填充模式和裁剪模式影响图像画面的展示细节视频质量是指生成的视频的输出参数，是一组参数决定的数值视频清晰度和文件大小分辨率图像分辨率则是单位英寸中所包含的像素点数，分辨率影响图像大小，与图像…
21年最新Python面试题及答案汇总详解(上)
错过三月找工作的机会，还要错过四月的好时期吗?Python面试你做准备了吗?下面小编整理了一套2021年最新Python常见面试题目，及Python面试题目答案汇总。希望能够帮助到大家。 21年最新Python面试题及答案汇总详解(上) 1、列表(list)和元组(tuple)有什么…
sina微博api源码阅读之函数
1. array_map将类的静态成员函数作为回调函数用在指定的单元上，可以递归调用 public static function urlencode_rfc3986($input) { if (is_array($input)) { return array_map(array(OAuthUtil, urlencode_rfc3986), $input); } else …
LeetCode实战：将有序数组转换为二叉搜索树
题目英文 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by mo…
Spring、Spring Boot和TestNG测试指南 - @ActiveProfiles
Github地址 ActiveProfiles可以用来在测试的时候启用某些Profile的Bean。本章节的测试代码使用了下面的这个配置： Configuration public class Config {BeanProfile("dev")public Foo fooDev() {return new Foo("dev");}BeanProfile("prod…
python语言中如何使用注释
每一种计算机语言都有自己的注释方式，我们知道注释的作用是解释这些代码，方便程序员以后的检查和修改。而且注释的一部分在运行程序的过程中不起作用，也不会显示出来。下面我们将为大家介绍，在python语言中如何使用注释? 在pytho…
RHEL5(CentOS)下nginx+php+mysql+tomcat+memchached配置全过程(转)
RHEL5(CentOS)下nginxphpmysqltomcatmemchached配置全过程 一、准备工作： SSH,telnet终端中文显示乱码解决办法 vi /etc/sysconfig/i18n将内容改为 LANG"zh_CN.GB18030" LANGUAGE"zh_CN.GB18030:zh_CN.GB2312:zh_CN" SUPPORTED"zh_CN.GB18…
LeetCode实战：搜索二维矩阵
题目英文 Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted from left to right.The first integer of each row is greater than the last integer of the previou…
windows指令
为什么80%的码农都做不了架构师？>>> C:\Windows\System32\drivers\etc nbtstat -a 1.7.2.2s 检查该IP的主机名称 WExNmU5Z windows启动配置界面 在“运行”中输入“msconfig mstsc -admin 远程 虚拟机的判断：如果有vmtoolsd.exe进程就是虚拟…
Java培训好不好?零基础可以学吗?
5g时代的来临，越来越多的人开启智能时代，互联网行业的发展速度越来越快，高薪行业一直受到很多人的关注，尤其是java这一块，很多人都想学习，那么参加Java培训好不好?零基础可以学吗? Java培训好不好?零基础…
顺水行舟，逆水行舟
水，或温柔，或猛烈 万物皆可比喻为水 顺水行舟，逆水行舟，皆为操船者智慧之体现 翻船者。。。把船搞翻了几回还执意而为，SB也。。。转载于:https://www.cnblogs.com/Zetazzz/archive/2011/01/30/1948082.html
LeetCode实战：二叉树的最大深度
题目英文 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,n…
jfinal整合shiro回顾
2019独角兽企业重金招聘Python工程师标准>>> 目前jfinal使用shiro进行身份验证和授权的后台实现已完成，现在我再来总结下学习过程及代码实现过程。最近半年多项目开发都用.net，但又不甘心用了一年多的java，jfinal就这样被废弃&…
零基础学习Java培训有什么攻略
零基础学习Java培训有什么攻略?java是主流编程语言之一，我们在学习Java的时候需要制定Java学习路线图，Java涉及到的知识点非常的多，我们该从何学起呢?怎么系统的学习呢?来看看下面的详细介绍。 一、Java学习阶段 将Java学习过程分为3个阶段…
php去掉字符串的最后一个字符 substr()的用法
今天项目中用到，去掉字符串中的最后一个字符原字符串1,2,3,4,5,6,去掉最后一个字符","，最终结果为1,2,3,4,5,6代码如下：$str "1,2,3,4,5,6,"; $newstr substr($str,0,strlen($str)-1);echo $newstr;系统自带的函数也可…
如何加入LSGO软件技术团队？
背景 马上就要放暑假了！ LSGO软件技术团队 也要开始招新了！ 本次招入的同学，我会亲自来带，和你一起学习，共同成长。 我们的主要研究方向是机器学习，再详细一些就是视觉、自然语言处理和量化金融。 以下是…
《MySQL技术内幕：InnoDB存储引擎》读书笔记
2019独角兽企业重金招聘Python工程师标准>>> 1.InnoDB中每一页的大小默认为16kb，但是其也支持压缩页的功能，即将原本16kb的页压缩为1kb、2kb、4kb和8kb。当需要从缓存池中申请4kb大小的页时，MySQL的申请步骤如下： 检查…
UI设计要做什么，UI设计培训都要学什么
UI设计要做什么，UI设计培训都要学什么?相信有很多人都对这个问题比较感兴趣，近几年，UI设计被越来越多的人关注，行业薪资水平也是一路飙升，很多人都在准备学习UI设计，那么具体的内容，下面我们来…
[置顶] 如何搭建一个 Data Guard 环境
在Blog里零零散散的讲了一些DB 维护的东西，比较杂，也比较散。 这里就Oracle Data Guard 这块做一个小结。 主要是流程上的东西。 做个参考，以后装DG，照这个流程走就ok了。 一. 服务器设置1.1 硬盘的规划根据自己的业务量来规划硬…
技术图文：如何进行代码的重构？以封装 BigOne API 为例
背景 自从把“量化交易”作为自己精进的技术方向之后，我做了一些准备工作。 比如： 1. 爬取交易所的公告，根据公告的信息来研判数字货币的短期走势。 这里面有一个“流动性溢价”的概念，等后面我会结合一些例子跟大家聊聊这块的…
《Java核心技术 卷Ⅱ 高级特性（原书第10版）》一3.7.5 使用StAX写出XML文档
3.7.5 使用StAX写出XML文档 在前一节中，你看到了如何通过写出DOM树的方法来产生XML文件。如果这个DOM树没有其他任何用途，那么这种方式就不是很高效。StAX API使我们可以直接将XML树写出，这需要从某个OutputStream中构建一个XMLStreamWriter…
大数据就业前景怎么样?需要学会哪些技术?
智能时代的来临，我们日常生活中的很多技术都可以用大数据来实现，大数据开发行业做为IT行业中的一类更是前景无限。所以很多人想转行做大数据开发。那么现在大数据就业前景怎么样?需要学会哪些技术? 大数据就业前景怎么样?需要学会哪些技术?大数据行业…
技术图文：如何利用 C# 实现 误差反向传播 学习规则？
背景 我们在 如何利用 C# 对神经网络模型进行抽象？ 中完成了神经网络的抽象结构： 三个接口：激活函数、有监督学习、无监督学习 三个抽象类：神经元、网络层、网络拓扑 我们在 如何利用 C# 实现神经网络的感知器模型？ …
SQL注入漏洞全接触--入门篇
随着B/S模式应用开发的发展，使用这种模式编写应用程序的程序员也越来越多。但是由于这个行业的入门门槛不高，程序员的水平及经验也参差不齐，相当大一部分程序员在编写代码的时候，没有对用户输入数据的合法性进行判断，使…
WannaCry 不相信眼泪 它需要你的安全防御与响应能力
在过去的几天里，WannaCry恶意软件及其变体影响了全球数百家组织与机构。 尽管每个组织都会因各种各样的原因没能及时对存在漏洞的系统做更新保护，或者担心更新实时系统的风险，两个月对于任何组织来用于采取措施保证系统安全也并不算太短的时间…
小白阶段如何学习Web前端知识
学会了UI设计技术，接下来的计划就是要找工作了，UI设计在面试环节的自我介绍很重要，有时候一分钟的自我介绍已经足够让HR判断出你适不适合他们公司，那做为一名UI设计师面试时如何自我介绍呢?来看看下面的详细介绍。 UI设计师面试时…
康泰瑞影推高性能3D/4D超声可视化方案
本文讲的是康泰瑞影推高性能3D/4D超声可视化方案,康泰瑞影(ContextVision)推出的业界首款超声实时3D立体图像增强产品已经配备全新的影像可视化功能。所推出的产品REALiCE?将提供逼真的3D超声影像，提高了诊断质量。 REALiCE软件将GOPiCE?自适应3D/4D立体图像增强产…
New Video Game Controlled By Kissing
unassimilatible writes "Artist Hye Yeon Nam has put her video game where her mouth is — literally — with the creation of a new bowling game thats controlled only by passionate (and awkward) French kissing. The Kiss Controller, as its called, has two…
资料分享：数学建模资料分享 -- 图论部分
背景 今天上午，在教六第一阶梯教室为数学建模俱乐部的同学们分享了有关图论的基本知识和应用。 课后，为同学们留了一个算法实现的小练习，大家可以先做一下。在本图文的末尾处，我把上课的资料以及代码分享出来，供大家…