本文目录一览：
- 1、Kruskal算法的时间复杂度是多少？
- 2、kruskal算法
- 3、克鲁斯卡尔算法的算法描述
- 4、Prim算法和Kruskal算法的区别是什么？
- 5、最小生成树实际应用的例子
- 6、最小生成树 普里姆算法和克鲁斯卡尔算法
- 7、最小生成树的两种算法？
- 8、kruskal算法是贪心吗
- 9、kruskal算法的举例描述
Kruskal算法的时间复杂度是多少？
log的底数为2，即e乘以以2为底的e的对数
Kruskal算法的时间复杂度由排序算法决定，若采用快排则时间复杂度为O(N log N)。
kruskal算法：
求加权连通图的最小生成树的算法。kruskal算法总共选择n- 1条边，（共n个点）所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的
具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。kruskal算法分e 步，其中e
是网络中边的数目。按耗费递增的顺序来考虑这e
条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设WN=(V,{E})是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的
过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n
棵树的一个森林。之后，从网的边集 E
中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶
点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
kruskal算法
kruskal算法指克鲁斯卡尔算法。
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树 。
克鲁斯卡尔（Kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网G=（V，E），令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），概述图中每个顶点自成一个连通分量。
在E中选择代价最小的边，若该边依附的顶点分别在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至T中所有顶点构成一个连通分量为止。
克鲁斯卡尔算法的时间复杂度主要由排序方法决定，而克鲁斯卡尔算法的排序方法只与网中边的条数有关，而与网中顶点的个数无关，当使用时间复杂度为O（elog2e）的排序方法时，克鲁斯卡尔算法的时间复杂度即为O（log2e），因此当网的顶点个数较多、而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果较好。
克鲁斯卡尔算法的算法描述
克鲁斯卡尔算法的时间复杂度为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）。
Prim算法和Kruskal算法的区别是什么？
Prim算法和Kruskal算法都是用于在连通图中寻找最小生成树的经典算法，但它们在实现过程中存在一些区别：
1. 实现过程：Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal算法需要先对权重排序后查找。
2. 算法效率：Kruskal算法在效率上比Prim算法快，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到。
3. 贪心策略：Prim算法和Kruskal算法都采用了贪心策略，但它们的侧重点不同。Prim算法更注重在每次迭代中找到权重最小的边，而Kruskal算法则注重在对边进行排序后，选择权重大小的边进行加入。
4. 初始化方法：Prim算法从一棵空的生成树开始，通过不断寻找邻边的最小权重顶点来构建最小生成树。而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算法需要使用最小堆来进行节点的选择和边的计算，需要注意最小堆的实现和使用方法，以确保算法的正确性和效率。
最小生成树实际应用的例子
最小生成树实际应用的例子如下：
Kruskal算法，过程描述：始终以边为主导地位，先选择权值最小的边，总是选择当前可用最小权值边，并且每次判断两点之间是否已经间接连通，如果已经间接连通，则跳过此边。时间复杂度是O(n*logn)，适用于求边稀疏连通网的最小生成树。
Prim算法，过程描述：Prim算法始终以顶点为主导，并且起始点的选择是任意的。从起始点到其他点选择最小权值边，然后以此边两个顶点分别再找最小权值的边，同样已经间接连接的边跳过。时间复杂度是O(n2)，适用于求边稠密连通网的最小生成树。
要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
最小生成树性质与算法简述：
最小生成树性质：设G=(V，E）是一个连通网络，U是顶点集V的一个非空真子集。若(u，v）是G中一条“一个端点在U中（例如：u∈U），另一个端点不在U中的边（例如：v∈V-U），且（u，v）具有最小权值，则一定存在G的一棵最小生成树包括此边（u，v）。
将集合U中的顶点看作是红色顶点，②而V-U中的顶点看作是蓝色顶点，③连接红点和蓝点的边看作是紫色边，④权最小的紫边称为轻边（即权重最“轻”的边）。于是，MST性质中所述的边（u，v）就可简称为轻边。
求MST的一般算法可描述为：针对图G，从空树T开始，往集合T中逐条选择并加入n-1条安全边（u，v），最终生成一棵含n-1条边的MST。
Kruskal算法简述：假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。
最小生成树 普里姆算法和克鲁斯卡尔算法
#include
#include
#define N 100
int length;
typedef struct
{ int num;
int tag;
}NODE;
typedef struct
{ int cost;
int node1;
int node2;
}EDGE;
NODE set[N]; /* 节点集, n为连通网的节点数 */
EDGE es[N]; /* 边集, m为连通网的边数 */
EDGE st[N]; /* 最小生成树的边集 */
int InsertSort(EDGE *dat,int n)
{
int i,item,j,m,h;
for(i=0;i
item=dat[i].cost;
m=dat[i].node1;
h=dat[i].node2;
if(i==0){ j=0; dat[j].cost=item; }
else
{
j=i-1;
while((item
{
dat[j+1].cost=dat[j].cost;
dat[j+1].node1=dat[j].node1;
dat[j+1].node2=dat[j].node2;
j--;
}
dat[j+1].cost=item;
dat[j+1].node1=m;
dat[j+1].node2=h;
}
}
printf("权值排序结果(升序)：\n");
for(i=0;i
}
int Find(NODE *set,int elem)
{
int i,j,k;
i=elem;
while(set[i].tag>=0) { i=set[i].tag; }
j=elem;
while(j!=i) { k=set[j].tag; set[j].tag=i; j=k;}
return i;
}
int Union( NODE *set,int elem1, int elem2)
{
int m,n,sum;
m=Find(set,elem1);
n=Find(set,elem2);
sum=set[m].tag+set[n].tag;
if(set[m].tag>set[n].tag) { set[n].tag=sum; set[m].tag=n; }
else { set[m].tag=sum; set[n].tag=m; }
}
int Ququanzhi(EDGE *es,int n)
{
int i,j=0,len;EDGE b[N];
for(i=0;i<=n;i++)
{
if(es[i].cost>0)
{
b[j].cost=es[i].cost;
b[j].node1=es[i].node1;
b[j].node2=es[i].node2;
j++;
}
}
len=j;
printf("\n");
for(i=0;i
es[i].cost=b[i].cost;
es[i].node1=b[i].node1;
es[i].node2=b[i].node2;
}printf("\n");
return len;
}
int Kruskal(EDGE *es, NODE *set, int length, EDGE *st,int num)
{
int i,j,k=1,m,n,mincost=0;
st[0].cost=es[0].cost;
st[0].node1=es[0].node1;
st[0].node2=es[0].node2;
m=Find(set,st[0].node1);
n=Find(set,st[0].node2);
Union(set,m,n);
mincost+=es[0].cost;
for(i=1;i
m=Find(set,es[i].node1);
n=Find(set,es[i].node2);
if(m!=n)
{
Union(set,m,n);
st[k].cost=es[i].cost;
st[k].node1=es[i].node1;
st[k].node2=es[i].node2;
mincost+=es[i].cost;
k++;
}
if(k==num) break;
}
printf("\n最小权值边和：mincost=%d\n",mincost);
printf("\n最小树的边数：%d\n\n",k);
return k;
}
void Output(EDGE *st, int n)
{
int i;
printf("最小生成树的为：\n\n");
for(i=0;i
printf("树边%d :%3d<-->%d=%d\n",i+1,st[i].node1+1,st[i].node2+1,st[i].cost);
}
}
int main()
{
int i,j,k=0,L,temp,len;NODE *p,*q;
textbackground(BLUE);
textcolor(YELLOW);
system( "graftabl 935 ");/*显示中文必须的代码*/
clrscr();
printf("请输入结点个数：");
scanf("%d",&length);
for(i=0;i
for(i=0;i
for(j=i+1;j
scanf("%d",&es[k].cost);
es[k].node1=i;
es[k].node2=j;
k++;
}
}
temp=k;
L=Ququanzhi(es,temp);/*提出权值大于0的边数*/
InsertSort(es,L); /*将权值递增排列*/
printf("\n");
len=Kruskal(es,set,L,st,length-1);
Output(st,len);
printf("\n树的表示：\n");
for(i=0;i
getch();
}
kruskal算法的时间复杂度主要由排序方法决定，其排序算法只与带权边的个数有关，与图中顶点的个数无关，当使用时间复杂度为O（eloge）的排序算法时，克鲁斯卡算法的时间复杂度即为O（eloge），因此当带权图的顶点个数较多而边的条数较少时，使用克鲁斯卡尔算法构造最小生成树效果最好！
克鲁斯卡尔算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。
普里姆算法
假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。
--以上传自http://hi.baidu.com/valyanprogramming/blog/item/1bc960e6095f9726b93820d9.html
1.Kruskal
//题目地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=1258
#include
#include
#include
using namespace std;
struct node
{
int v1;
int v2;
int len;
}e[10000];//定义边集
int cmp(const void *a,const void *b)//快排比较函数
{
return ((node*)a)->len-((node*)b)->len;
}
int v[100],a[100][100];//v为点集
void makeset(int n)
{
for(int i=0;i
}
int find(int x)
{
int h=x;
while(h!=v[h])
h=v[h];
return h;
}
int main()
{
int n,i,j,r1,r2,p,total;
while(scanf("%d",&n)!=EOF)
{
p=0;
total=0;
makeset(n);
for(i=0;i
for(j=0;j
scanf("%d",&a[i][j]);
e[p].v1=i;
e[p].v2=j;
e[p].len=a[i][j];
p++;
}
}
qsort(e,p,sizeof(e[0]),cmp);
for(i=0;i
r1=find(e[i].v1);
r2=find(e[i].v2);
if(r1!=r2)
{
total+=e[i].len;
v[r1]=r2;
}
}
printf("%d\n",total);
}
system("pause");
return 0;
}
2.Prim
//题目地址同上
#include
using namespace std;
#define M 101
#define maxnum 100001
int dis[M][M];
int prim(int n)
{
bool used[M]={};
int d[M],i,j,k;
for(i=1; i<=n; i++)
d[i] = dis[1][i];
used[1] = true;
int sum=0;
for(i=1; i
for(j=1; j<=n; j++){
if( !used[j] && d[j]
k = j;
}
}
used[k] = true;
sum += d[k];
for(j=1; j<=n; j++){
if( !used[j] && dis[k][j]
}
}
return sum;
}
int main()
{
int n,i,j;
while( cin>>n ){
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
scanf("%d",&dis[i][j]);
if( !dis[i][j] )
dis[i][j] = maxnum;
}
}
cout<
return 0;
}
代码来自网络
最小生成树的两种算法？
Prim算法 和 Kruskal算法
Prim算法逐次将最小权的边和相应顶点加到集合中，适合于求边稠密的最小生成树；Kruskal算法先将所有边都放入集合，然后再逐个选择最小权的边，适合于求稀疏的网的最小生成树。
详细过程请参考相关资料
Prim算法
Kruskal算法
主要有两个：
1.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。
kruskal算法是贪心吗
Kruskal算法是一个基于贪心思想的算法，用于求解最小生成树的问题。
贪心算法是一种求解优化问题的算法，通过每一步选择局部最优解来得到全局最优解。在Kruskal算法中，我们首先将所有边按照权值从小到大进行排序，然后逐一考虑每条边，如果该边所连接的两个端点不在同一个连通块中，就将其加入最小生成树中，否则就将其舍弃。
这样做的正确性可以通过反证法来证明。假设存在一个更优的生成树，但是在构建这个生成树的过程中，我们选择了不按照边权值从小到大排序的边。我们可以将这个生成树变换成已按照边权值从小到大排序的边构成的生成树，这个新的生成树的权值要小于原来的生成树。因此，只有按照边权值从小到大排序的边构成的生成树才是最小生成树。
Kruskal算法的时间复杂度为O(ElogE)，其中E为边的数量。因此，Kruskal算法是一种高效而又简单的求解最小生成树问题的方法，被广泛应用于实际问题中。
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），应该是必须保证新边的两个端点至少有一个不包含于原边集的端点集中，其中每一个连通子图都建立一个单独的端点集。
