Prim kruskal 最小生成树算法和并查集

prim算法的思路比较简单,是一种贪心策略,也有严格的数学证明,证明这种算法是正确的(反证和归纳)

思路:随机选一个点作为开始,每次选择权重最小的那条边和连接的节点加入最小生成树。

实现过程中需要可以利用优先队列这种数据结构来对动态添加的候选边进行临时存储以提高效率。

kruskal算法的思路也是贪心的,也有严格的数学证明。

思路:首先对所有的边按照权重进行排序,选择权重最小的那条边作为初始化的边集合。便利按照权重排序好的边,如果某条边的两个节点属于两个不同的联通分量,则将这条边加入最小生成树,并合并这两个连通分量。

具体的实现过程会用到并查集这种数据结构,也可以认为它是一颗二叉树,实际编码过程中可以用数组来存储这种并查集的结构,数组的值就代表父亲节点的索引。

并查集练习:Leetcode 990. 等式方程的可满足性

发表评论

电子邮件地址不会被公开。 必填项已用*标注