对最小生成树的两种算法感悟
2021-03-23 13:25
标签：就是 com 状态 离散数学 离散 代码 过程 更新 amp 请注意，该讲解不提供代码模板。 也算是傻愣愣地熟悉一下两种不同的思路了吧。 首先，不得不说Prim算法以及Kruskal算法确实是两个十分优秀的算法。 1、说一说Prim算法吧 Prim算法的核心在于分割开了已经进入生成树的结点集合和还未进入生成树的结点集合两类。 我在模板题提供的代码模板 已经进入生成树的结点被vis标记，还未进入生成树的结点没有被vis标记。 上面这一段的叙述，基本上就是Prim算法在解决最小生成树时的核心思路了。 2、Kruskal算法 这个算法其实就是离散数学教材上所说的避圈法：将所有边按照权值从小到大依次递增排列， 在具体实现过程中，"避免形成圈"依然采用了Prim中的思想，借助vis数组检验即可实现： 3、如何对已经进入生成树的结点和还未进入生成树的结点进行标记？ 一种最简单暴力的方法就是 OK 对最小生成树的两种算法感悟 标签：就是 com 状态 离散数学 离散 代码 过程 更新 amp 原文地址：https://www.cnblogs.com/savennist/p/13846491.html
模板题目请走这里
它们分别从点和边的角度出发建立一个最小的权值树。
在实现过程上，也有诸多注意点要说~~
类似图的二分过程，我们寻找的每一条边必须是跨越这两个集合的边，并且每次能够使用的一定还是一个权值最小的边。
中由lowc数组协同vis数组一同实现了上述核心步骤。
如果vis[p]没有被标记 && lowc[p]的值最小，那么p就可以作为生成树的新结点加入生成树。
对于每一个新加入生成树的结点p而言，lowc数组都需要根据v的邻接边的权值进行更新。
之后，lowc数组中一定存在一个边权值，是当前状态下生成树结点集合与非生成树结点集合间的相连边e。
(当然，如果e不存在，那么这张图本身就无法生成一个最小生成树了.....)
随着lowc与vis的配合，生成树中的每一个边的权值以及它对应的一个端点也都会被安全地保存在lowc中。
然后从权值小的边开始逐一选入生成树中，同时要避免后加入的边与前面的边形成圈。
因为，形成圈的一定是当前待选边的两个端点u,v都被vis数组标记了。
也就是说，如果vis[u]被标记 && vis[v]被标记那么边e(u,v)一定不会进入生成树。
未完....