前言
你好，我是小黄，一名独角兽企业的Java开发工程师。 感谢茫茫人海中我们能够相遇， 俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习， 希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。
一、引言
大家有没有在生活中遇到这种事情
你们县城需要在几个小区之间进行修路，由于*资金紧张，不可能所有的小区之间都进行修路，而是利用最少的资金修一条可以连接所有小区的路
如同下图所示：
当然，上述只是一个抽象化的例子，而我们实际生活中，每个小区间的距离也是不一样的，我们怎么使用最小的资金去连接所有的小区呢？
这就牵扯到我们今天的老大哥们：Kruskal 算法和 Prim 算法
这两种算法分别从边和点产生最小生成树，保证了资金的最小性
本篇文章，我们一起走近 Prim 算法，探究一下该算法是怎么通过点来确定最小生成树的
PS：Kruskal 算法链接：最小生成树——Kruskal 算法
二、Prim 算法是什么
普里姆算法（Prim算法），图论中的一种算法，通过 点去找边 的行为，可在加权连通图里搜索最小生成树。
该算法于1930年由捷克数学家 沃伊捷赫·亚尔尼克 发现；并在1957年由美国计算机科学家 罗伯特·普里姆 独立发现
我们以下面的小区为例，通过 Prim 算法会给我们一条连接所有小区的最短路径
三、Prim 算法本质
对于 Prim 算法来说，整体使用了 贪心 的思想
简单的来说，我们需要从上述图中随机挑选一个点，找到最小的边，然后释放其连接的点，再去找到最小的边，周而复始......
PS：每个边只入队一次
- 我们随机选中
A小区这个节点，将其所有的边2、3、6释放出来，我们的边集合为2、3、6，找到最小的边2用掉，释放E小区
- 我们选中
E小区这个节点，将其所有的边7、12释放出来，我们的边集合为3、6、7、12，找到最小的边3用掉，释放B小区
- 我们选中
B小区这个节点，将其所有的边10释放出来，我们的边集合为6、7、10、12，找到最小的边6用掉，释放D小区
- 我们选中
D小区这个节点，将其所有的边1释放出来，我们的边集合为1、7、10、12，找到最小的边1用掉，释放C小区
这样，我们所有的点已经找出来了
可以看到我们的最小生成树为：12
我们对比一下上期讲到的 Kruskal 算法：Kruskal 算法
我们可以看到，得到的路径都是一样的，证明 Kruskal 和 Prim 算法求出的最小生成树相同
四、Prim 算法实现
对于 Prim 算法，主要利用贪心的思想，由点去寻找边，解锁点的循环.....
4.1 比较器的实现（按照边的权重排序）
public static class MyEdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge o1, Edge o2) {
return o1.weight - o2.weight;
}
}
复制代码4.2 Prim 算法
public Set<Edge> prim(Graph graph) {
// 解锁的边
PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new MyEdgeComparator());
// 该点是否走过
Set<Node> setNodeVis = new HashSet<>();
// 挑选的边
Set<Edge> setEdge = new HashSet<>();
for (Node node : graph.nodes.values()) {
// 该点没有被走过
if (!setNodeVis.contains(node)) {
// 将该点标记为已经被走过
setNodeVis.add(node);
// 加入该点解锁的边
for (Edge edge : node.edges) {
priorityQueue.add(edge);
}
// 由边找点
while (!priorityQueue.isEmpty()) {
Edge edge = priorityQueue.poll();
Node to = edge.to;
// 看当前点是否被访问过
if (!setNodeVis.contains(to)) {
// 最终的结果
setEdge.add(edge);
// 没有访问的话，加入访问标记，并且将其所有的边给放进去
setNodeVis.add(to);
for (Edge edge1 : to.edges) {
priorityQueue.add(edge1);
}
}
}
}
// 大家可以思考一下这里的 break 存在的意义是什么
break;
}
return setEdge;
}
复制代码以上图的描述均使用图的形象化描述：图的形象化描述
五、总结
通过以上的描述，我们可以解决我们开头说的那个问题：你们县城需要在几个小区之间进行修路，由于*资金紧张，不可能所有的小区之间都进行修路，而是利用最少的资金修一条可以连接所有小区的路
同时，对于 Prim 的代码也需要多写几遍，多想想 Kruskal 和 Prim 的区别
对源代码有兴趣的小伙伴，可以关注 爱敲代码的小黄 公众号，回复：算法源码 即可获得算法源码
回答一下 break 的问题：防止森林现象的存在
本期的内容就到这里，下期会讲述最短路径 Dijkstra