上篇博客我们聊了图的物理存储结构邻接矩阵和邻接链表，然后在此基础上给出了图的深度优先搜索和广度优先搜索。本篇博客就在上一篇博客的基础上进行延伸，也是关于图的。今天博客中主要介绍两种算法，都是关于最小生成树的，一种是Prim算法，另一个是Kruskal算法。这两种算法是很经典的，也是图中比较重要的算法了。
今天博客会先聊一聊Prim算法是如何生成最小生成树的，然后给出具体步骤的示例图，最后给出具体的代码实现，并进行测试。当然Kruskal算法也是会给出具体的示例图，然后给出具体的代码和测试用例。当然本篇博客中的Demo是在上篇博客的基础上进行实现的。因为在上篇博客中我们已经创建好了现成的图了，本篇博客就拿过来直接使用。
在本篇博客的开头呢，先简单的聊一下什么是最小生成树。最小生成树是原图的最小连通子图，也就是说该子图是连通的并且没有多余的边，更不会形成回路。最重要的是最小生成树的所有边的权值相加最小，这也是最小生成树的来源。与现实生活中联系起来那就是一些村庄要通电话线，如何让每个村都可以通电话线并且最省材料。换句话说，是每个村庄连通，并且总线路最短，如果线连接完毕后，其实就是我们本篇博客要聊的最小生成树。
一、普利姆算法
接下来我们就来聊Prim算法。其实Prim算法创建最小生成树的主要思路就是从候选节点中选择最小的权值添加到最小生成树中。下图是我们之前创建的图使用Prim算法创建最小生成树的完整过程。红色的边就是每一步所对应的候选节点做连的弧，从这些候选的边中选出权值最小的边添加到最小生成树中，我们可以将其视为转正的过程。
延伸阅读
- ssh框架 2016-09-30
- 阿里移动安全 [无线安全]玩转无线电——不安全的蓝牙锁 2017-07-26
- 消息队列NetMQ 原理分析4-Socket、Session、Option和Pipe 2024-03-26
- Selective Search for Object Recognition 论文笔记【图片目标分割】 2017-07-26
- 词向量-LRWE模型-更好地识别反义词同义词 2017-07-26
- 从栈不平衡问题 理解 calling convention 2017-07-26
- php imagemagick 处理 图片剪切、压缩、合并、插入文本、背景色透明 2017-07-26
- Swift实现JSON转Model - HandyJSON使用讲解 2017-07-26
- 阿里移动安全 Android端恶意锁屏勒索应用分析 2017-07-26
- 集合结合数据结构来看看(二) 2017-07-26
学习是年轻人改变自己的最好方式