最小生成树就是在一个图中找到一条树,这些树可以包括图中所有的点并且这些 边权重的代价是最低的。如下图:

在本章中,我们将讨论两个最小生成树的算法:克鲁斯卡尔(Kruskal)算法和普利姆(Prim)算法,这两种算法均是使用贪心策略来完成最小生成树的生成,但是他们所使用的具体方式却有所不同。

1.Kruskal算法

Kruskal算法的核心是寻找当前图中权重最低的边,如果他们属于不同的集合则添加进最短路中(如下图第四行第二图,找到最小权重边7后并没有加入到最短路中去),最后将多生成森林组成成一棵树。

2.Prim算法

prim依然利用了贪心的思想,只不过他不在全局上找权重最低的边,而是不断的从当前集合出发,找当前集合中点的最短出度边,以此来构造最短生成树。


1 条评论

网红教主孙筱语 · 2020-01-11 07:23

Unknown Unknown Unknown Unknown

煜萌萌,你会三对角矩阵的并行算法吗?托马斯矩阵算法?

发表回复

Avatar placeholder

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