×

克鲁斯卡尔算法,prim和kruskal算法的区别

admin admin 发表于2023-12-11 14:45:24 浏览16 评论0

抢沙发发表评论

本文目录一览：

kruskal算法是什么？

kruskal算法是求加权连通图的最小生成树的算法。
kruskal算法总共选择n- 1条边，(共n个点)所使用的贪心准则是:从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。
kruskal算法分e步，其中e是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
Kruskal算法基本思想：
每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量。
排序使用Quicksort(O(eloge))。
检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数。
Union-Find使用rank启发式合并和路径压缩。
总复杂度O(eloge)=O(elogv) (因为e

图的相关算法（二）：最小生成树算法

在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
例如，对于上图中的连通网可以有多棵权值总和不相同的生成树。
克鲁斯卡尔（Kruskal）算法，是用来求加权连通图的最小生成树的算法。
基本思想 ：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法 ：首先构造一个只含n个顶点的森林，然后依照权值从小到大从连通网中选择边加入到森林中，并使得森林不产生回路，直到森林变成一棵树为止。
以图G4为例（更详细的可以参考《算法导论》p367），对Kruskal进行演示（假设，用数组R保存最小生成树结果）。
第1步 ：将边加入R中。 边的权值最小，因此将它加入到最小生成树结果R中。 第2步 ：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。 第3步 ：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。 第4步 ：将边加入R中。 上一步操作之后，边的权值最小，但会和已有的边构成回路；因此，跳过边。同理，跳过边。将边加入到最小生成树结果R中。 第5步 ：将边加入R中。 上一步操作之后，边的权值最小，因此将它加入到最小生成树结果R中。 第6步 ：将边加入R中。 上一步操作之后，边的权值最小，但会和已有的边构成回路；因此，跳过边。同理，跳过边。将边加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是： 。
根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题： 问题一 对图的所有边按照权值大小进行排序。 问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一用排序算法排序即可。 问题二，处理方式：记录顶点在“最小生成树”中的终点，顶点的终点是“在最小生成树中与它连通的最大顶点"(关于这一点，后面会通过图片给出说明)。然后每次需要将一条边添加到最小生成树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。 以下图来进行说明：
在将 加入到最小生成树R中之后，这几条边的顶点就都有了终点：
关于终点，就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是"与它连通的最大顶点"。 因此，接下来，虽然是权值最小的边。但是C和E的重点都是F，即它们的终点相同，因此，将加入最小生成树的话，会形成回路。这就是判断回路的方式。
普里姆（Prim）算法，也是求加权连通图的最小生成树的算法。
基本思想 对于图G而言，V是所有顶点的集合；现在，设置两个新的集合U和T，其中U用于存放G的最小生成树中的顶点，T存放G的最小生成树中的边。从所有的 u?U ，v?(V-U)（V-U表示除去U的所有顶点）的边中选取权值最小的边（u，v），将顶点v加入U中，将边（u,v）加入集合T中，如此不断重复，直到U=V为止，最小生成树构造完毕，此时集合T中包含了最小生成树中的所有边。
以上图G4为例，来对普里姆进行演示(从第一个顶点A开始通过普里姆算法生成最小生成树)。
初始状态 ：V是所有顶点的集合，即V={A,B,C,D,E,F,G}；U和T都是空！ 第1步 ：将顶点A加入到U中。 此时，U={A}。 第2步 ：将顶点B加入到U中。 上一步操作之后，U={A}, V-U={B,C,D,E,F,G}；因此，边(A,B)的权值最小。将顶点B添加到U中；此时，U={A,B}。 第3步 ：将顶点F加入到U中。 上一步操作之后，U={A,B}, V-U={C,D,E,F,G}；因此，边(B,F)的权值最小。将顶点F添加到U中；此时，U={A,B,F}。 第4步 ：将顶点E加入到U中。 上一步操作之后，U={A,B,F}, V-U={C,D,E,G}；因此，边(F,E)的权值最小。将顶点E添加到U中；此时，U={A,B,F,E}。 第5步 ：将顶点D加入到U中。 上一步操作之后，U={A,B,F,E}, V-U={C,D,G}；因此，边(E,D)的权值最小。将顶点D添加到U中；此时，U={A,B,F,E,D}。 第6步 ：将顶点C加入到U中。 上一步操作之后，U={A,B,F,E,D}, V-U={C,G}；因此，边(D,C)的权值最小。将顶点C添加到U中；此时，U={A,B,F,E,D,C}。 第7步 ：将顶点G加入到U中。 上一步操作之后，U={A,B,F,E,D,C}, V-U={G}；因此，边(F,G)的权值最小。将顶点G添加到U中；此时，U=V。
此时，最小生成树构造完成！它包括的顶点依次是：A B F E D C G。

prim和kruskal算法的区别

Prim算法和Kruskal算法的区别在于思想、适用范围、实现方式不同。
Prim算法是一种贪心算法，从一个点出发，每次选择权值最小的边连接到新的节点，直到所有节点都被遍历。而Kruskal算法是一种基于边的贪心算法，先将所有边按照权值从小到大排序，然后依次选取最小的边，加入到生成树中，直到生成树中含有所有节点。
Prim算法适用于稠密图，即节点较多、边数较多的情况；而Kruskal算法适用于稀疏图，即节点较多、边数相对较少的情况。
在同样的图结构下，Prim算法的时间复杂度为O(N^2)，其中N为节点数；而Kruskal算法的时间复杂度为O(ElogE)，其中E为边数，因此在边数较多的情况下，Kruskal算法更快。
Prim算法通常使用堆来实现，以便快速找到权值最小的边；而Kruskal算法通常使用并查集来实现，以便快速判断边是否连接了已有的生成树。总之，Prim算法和Kruskal算法都是求解最小生成树的有效算法，根据具体情况选择不同的算法可以提高计算效率。
使用Prim算法的注意事项
1、图的类型：Prim算法只适用于无向图，而且是连通图，如果是有向图或非连通图，则需要先进行转化或处理。
2、初始节点：Prim算法是从一个初始节点开始构建最小生成树，因此需要选择一个合适的初始节点，以保证最终的最小生成树是正确的。
3、节点标记：Prim算法需要对节点进行标记，以区分已经加入最小生成树的节点和还未加入的节点，需要注意标记的正确性和准确性。
4、权重计算：Prim算法的核心是计算边的权重，需要根据实际情况进行权重计算，以确保最终的最小生成树是正确的。
5、最小堆：Prim算法需要使用最小堆来进行节点的选择和边的计算，需要注意最小堆的实现和使用方法，以确保算法的正确性和效率。

最小生成树kruskal算法

最小生成树kruskal算法如下：
假设存在联通图，图中所有的顶点集合为，集合表示已经加入到生成树中的顶点集合，集合表示未加入到生成树中的顶点集合。
一开始，随机指定一个顶点加入到集合中，则，每次从集合与集合的顶点所构成的所有边中选取权值最小的一条边作为生成树的边，并将边在集合的那个顶点加入到集合中，如此下去直到集合中的全部顶点都加入到集合集合中，得到最小生成树。
所谓最小生成树，就是在一个具有N个顶点的带权连通图G中，如果存在某个子图G'，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G'的各边权值之和最小，则称G'为图G的最小生成树。
算法的介绍如下：
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。
这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation1和艾伦·图灵1937年提出的图灵机。

什么是Kruskal算法？如何避圈？

我知道是算法思想。
　　1. Kruskal算法
　　(1) 算法思想
　　K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
　　初始时没有任何边被选择。边（ 1 , 6）是最先选入的边，它被加入到欲构建的生成树中，得到图1 3 - 1 2 c。下一步选择边（ 3，4）并将其加入树中（如图1 3 - 1 2 d所示）。然后考虑边( 2，7 ，将它加入树中并不会产生环路，于是便得到图1 3 - 1 2 e。下一步考虑边（ 2，3）并将其加入树中（如图1 3 - 1 2 f所示）。在其余还未考虑的边中，（7，4）具有最小耗费，因此先考虑它，将它加入正在创建的树中会产生环路，所以将其丢弃。此后将边（ 5，4）加入树中，得到的树如图13-12g 所示。下一步考虑边（ 7，5），由于会产生环路，将其丢弃。最后考虑边（ 6，5）并将其加入树中，产生了一棵生成树，其耗费为9 9。图1 - 1 3给出了K r u s k a l算法的伪代码。

普里姆算法和克鲁斯卡尔算法区别

普里姆算法和克鲁斯卡尔算法区别如下：克鲁斯卡尔算法：是在剩下的所有未选取的边中，找最小边，如果和已选取的边构成回路，则放弃，选取次小边。普里姆算法：同样是在未选取的边中寻找最小边，但是选取的原则多了一条，就是该边必须和已选取的边相连，比如，如果边(1, 2)已被选取，那么接下来选取的边，必须是和顶点1，或者顶点2相连的。

最小生成树

所谓最小生成树，就是在一个具有N个顶点的带权连通图G中，如果存在某个子图G'，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G'的各边权值之和最小，则称G'为图G的最小生成树。 由定义我们可得知最小生成树的三个性质：
?最小生成树不能有回路。
?最小生成树可能是一个，也可能是多个。
?最小生成树边的个数等于顶点的个数减一。 本文将介绍两种最小生成树的算法，分别为克鲁斯卡尔算法(Kruskal Algorithm)和普利姆算法(Prim Algorithm)。

克鲁斯卡尔算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其构造，直到最后得到一颗最小生成树。
克鲁斯卡尔算法的执行步骤：
第一步：在带权连通图中，将边的权值排序；
第二步：判断是否需要选择这条边（此时图中的边已按权值从小到大排好序）。判断的依据是边的两个顶点是否已连通，如果连通则继续下一条；如果不连通，那么就选择使其连通。
第三步：循环第二步，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。
下面我用图示法来演示克鲁斯卡尔算法的工作流程，如下图：

什么是克鲁斯卡尔算法

设有一个有n个顶点的连通网N={V,E},最初先构造一个只有n个顶点，没有边的非连通图T={V, E},图中每个顶点自成一个连通分量。当在E中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。2算法描述编辑克鲁斯卡尔算法的时间复杂度为O（eloge）(e为网中边的数目)，因此它相对于普里姆算法而言，适合于求边稀疏的网的最小生成树。克鲁斯卡尔算法从另一途径求网的最小生成树。假设连通网N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{∮}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。例如图为依照克鲁斯卡尔算法构造一棵最小生成树的过程。代价分别为1，2，3，4的四条边由于满足上述条件，则先后被加入到T中，代价为5的两条边（1，4）和（3，4）被舍去。因为它们依附的两顶点在同一连通分量上，它们若加入T中，则会使T中产生回路，而下一条代价（=5）最小的边（2，3）联结两个连通分量，则可加入T。因此，构造成一棵最小生成树。上述算法至多对 e条边各扫描一次，假若以“堆”来存放网中的边，则每次选择最小代价的边仅需O（loge）的时间（第一次需O（e））。又生成树T的每个连通分量可看成是一个等价类，则构造T加入新的过程类似于求等价类的过程，由此可以以“树与等价类”中介绍的 mfsettp类型来描述T，使构造T的过程仅需用O（eloge）的时间，由此，克鲁斯卡尔算法的时间复杂度为O（eloge）。[1]

kruskal算法的举例描述

克鲁斯卡尔算法(Kruskal's algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分体现了贪心算法的精髓。大致的流程可以用一个图来表示。这里的图的选择借用了Wikipedia上的那个。非常清晰且直观。首先第一步，我们有一张图，有若干点和边第一步我们要做的事情就是将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择。排序完成后，我们率先选择了边AD。这样我们的图就变成了......第二步，在剩下的边中寻找。我们找到了CE。这里边的权重也是5......依次类推我们找到了6,7,7。完成之后，图变成了这个样子。......下一步就是关键了。下面选择那条边呢？ BC或者EF吗？都不是，尽管现在长度为8的边是最小的未选择的边。但是他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以我们不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是下图：......到这里所有的边点都已经连通了，一个最小生成树构建完成。Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
如果描述一条边采用的是二元组的方式来标识两个端点的话（a,b），应该是必须保证新边的两个端点至少有一个不包含于原边集的端点集中，其中每一个连通子图都建立一个单独的端点集。