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算法需要使用最小堆来进行节点的选择和边的计算，需要注意最小堆的实现和使用方法，以确保算法的正确性和效率。
Prim 算法和 Kruskal 算法
1).输入：一个加权连通图，其中顶点集合为V，边集合为E； 2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空； 3).重复下列操作，直到Vnew = V： a.在集合E中选取权值最小的边，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）； b.将v加入集合Vnew中，将边加入集合Enew中； 4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。 反证法 ：假设prim生成的不是最小生成树 1).设prim生成的树为G0 2).假设存在Gmin使得cost(Gmin)不属于G0 3).将加入G0中可得一个环，且不是该环的最长边(这是因为∈Gmin) 4).这与prim每次生成最短边矛盾 5).故假设不成立，命题得证. 1).记Graph中有v个顶点，e个边 2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边 3).将原图Graph中所有e个边按权值从小到大排序 4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中 如果这条边连接的两个节点于图Graphnew中不在同一个连通分量中，添加这条边到图Graphnew中 归纳基础： n=1，显然能够找到最小生成树。 归纳过程： 假设Kruskal算法对n≤k阶图适用，那么，在k+1阶图G中，我们把最短边的两个端点a和b做一个合并操作，即把u与v合为一个点v'，把原来接在u和v的边都接到v'上去，这样就能够得到一个k阶图G'(u,v的合并是k+1少一条边)，G'最小生成树T'可以用Kruskal算法得到。 我们证明T'+{}是G的最小生成树。 用反证法，如果T'+{}不是最小生成树，最小生成树是T，即W(T)})。显然T应该包含，否则，可以用加入到T中，形成一个环，删除环上原有的任意一条边，形成一棵更小权值的生成树。而T-{}，是G'的生成树。所以W(T-{}))=W(T'+{})，产生了矛盾。于是假设不成立，T'+{}是G的最小生成树，Kruskal算法对k+1阶图也适用。 由数学归纳法，Kruskal算法得证。
克鲁斯卡尔时间复杂度怎么算出来的
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
kruskal算法：
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设WN=(V,{E})是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的
过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n
棵树的一个森林。之后，从网的边集 E
中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶
点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
什么样的图最小生成树唯一？
如果一个图的各个边的权值各不相同，那么它的最小生成树是唯一的。n个点用n-1条边连接，形成的图形只可能是树。可以这样理解：树的每一个结点都有一个唯一的父亲，也就是至少有n条边，但是根节点要除外，所以就是n-1条边。那么，对于一张n个点带权图，它的生成树就是用其中的n-1条边来连接这n个点，那么最小生成树就是n-1条边的边权之和最小的一种方案，简单的理解，就是用让这张图只剩下n-1条边，同时这n-1条边的边权总和最小。红边即为此图的最小生成树。树形图的概念无圈且连通的无向图称为树。树一般记为T。作为树定义还可以有以下几种表述：（1）T 连通且无圈或回路。（2）T无圈且有n－1条边（如果有n个结点）。（3）T连通有n－1条边。（4）T无回路，但不相邻的两个结点之间联以一边，恰得一个圈。（5）T连通，但去掉T的任意一条边，T就不连通了。（亦即在点集合相同的图中，树是含边数最少的连通图。）（6）T的任意两个结点之间恰有一条初等链。
最小生成树可以用在什么领域
最小生成树应用于图论知识的实际问题。生成树和最小生成树有许多重要的应用。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。生成树协议工作原理：任意一交换机中如果到达根网桥有两条或者两条以上的链路。生成树协议都根据算法仅仅保留一条，把其他切断，从而保证任意两个交换机之间只有一条单一的活动链路。因为这种生成的这种拓扑结构，很像是以根交换机为树干的树形结构，故为生成树协议。以上内容参考：百度百科-最小生成树以上内容参考：百度百科-生成树协议
