本文目录
- 最小生成树的两种算法
- 克鲁斯卡尔算法可以回到起始点吗
- kruskal算法是什么
- 克鲁斯卡尔算法
- 谁能说说为什么kruskal算法不能应用于边权为负的情况而非要用bellman算法
- prim和kruskal算法的区别
- 克鲁斯卡尔算法是求图的什么
- 克鲁斯卡尔算法介绍
- 克鲁斯卡尔算法一定要画图吗
- 什么是克鲁斯卡尔算法
最小生成树的两种算法
主要有两个：1.普里姆（Prim)算法 特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。2.克鲁斯卡尔（Kruskal)算法 特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。
克鲁斯卡尔算法可以回到起始点吗
可以。克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。 具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
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)/2)。
克鲁斯卡尔算法
你确定要用邻接表吗？因为在克鲁斯卡尔算法里只需要存储边及费用，用邻接表意义不大，还不好排序。以下给出并查集实现的克鲁斯卡尔算法，求解生成网络的最小费用，并输出生成网络里的路径。#include《iostream》#include《algorithm》using namespace std;int p;int cho;struct edge{ int u,v,w;//u表示起始点编号，v表示终点编号，w表示该路径费用}e;int n,m;//n表示点的个数，m表示路径数void Init(){ int i; for(i=1;i《=n;i++) { p=i; rank=0; }}bool cmp(edge a,edge b){ return a.w《b.w;}int Find(int t){ if(p!=t) { p); } return p;}int Union(int a,int b){ int x,y; x=Find(a); y=Find(b); if(rank) { p=x; } else { p=y; if(rank) rank++; } return 0;}int main(){ scanf("%d%d",&n,&m); int i,j; for(i=0;i《m;i++) { scanf("%d%d%d",&e.w); } Init(); sort(e,e+m,cmp); int cnt=0,ans=0; for(i=0;i《m;i++) { if(Find(e.v)) { cnt++; ans+=e.w; Union(e.v); cho=i; if(cnt==n-1) break; } } printf("%d\n",ans); for(j=1;j《=cho;j++) { printf("%d %d\n",e.v); } return 0;}
谁能说说为什么kruskal算法不能应用于边权为负的情况而非要用bellman算法
你是否弄错了，是单源最短路径的Dijkstra算法不能边权为负值，因为其算法为从当前最小路径长度开始，逐步增加，并且不再回头运算，如果有边权为负值，自然用bellman算法还有一个可以选择的是Floyd算法，这后面两者的使用前提都是不存在负权回路，原因是一圈转下来变小了，再转一圈就更小了而Kruskal算法是求最小生成树的，边权为负值什么问题都没有
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算法prim适合用于稠密图，kruskal适合用于稀疏图两种算法都是以贪心为基本思想的~满意望采纳谢谢！！！！
克鲁斯卡尔算法介绍
1、克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。 2、克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止 。
克鲁斯卡尔算法一定要画图吗
1）克鲁斯卡尔算法概念克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树（2）实现思路对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树；
什么是克鲁斯卡尔算法
设有一个有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）。
