prim和kruskal算法时间复杂度
刘耀文的大沙雕
钟意阿满
利用Prim（普里姆）算法 构造最小生成树 程序
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<cstdio>。
#include<cstdlib>。
#include<iostream>。
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<n;i++)。
v[i]=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<n;i++)。
{
for(j=0;j<n;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<p;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 <iostream>。
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<n; i++){。
int temp=maxnum;。
for(j=1; j<=n; j++){。
if( !used[j] && d[j]<temp ){。
temp = d[j];。
k = j;
}
}
used[k] = true;。
sum += d[k];。
for(j=1; j<=n; j++){。
if( !used[j] && dis[k][j]<d[j] )。
d[j] = dis[k][j]; // 与Dijksta算法的差别之处。
}
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<<prim(n)<<endl;。
return 0;
代码来自网络
抱起亚轩找小葵
什么是Prim算法?
算法同样是解决最小生成树的问题。
其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。
与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。
复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。
Prim算法用于求无向图的最小生成树。
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)。
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}。
大圣杰锅是
2015考研：计算机数据结构常用算法（7）？
Prim算法
Prim算法用于求无向图的最小生成树。
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)。
Prim算法实现：
（1）集合：设置一个数组set[i](i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
参考程序
/* Prim.c
Copyright (c) 2002, 2006 by ctu_85。
All Rights Reserved.。
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */。
#include "stdio.h"。
#define maxver 10。
#define maxright 100。
int main()
int G[maxver][maxver],in[maxver]=,path[maxver][2];。
int i,j,k,min=maxright;。
int v1,v2,num,temp,status=0,start=0;。
restart:
printf("Please enter the number of vertex(s) in the graph:\n");。
scanf("%d",&num);。
if(num>maxver||num<0)。
printf("Error!Please reinput!\n");。
goto restart;
for(j=0;j<num;j++)。
for(k=0;k<num;k++)。
if(j==k)
G[j][k]=maxright;。
else
if(j<k)
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);。
scanf("%d",&temp);。
if(temp>=maxright||temp<-1)。
printf("Invalid input!\n");。
goto re;
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;。
for(j=0;j<num;j++)。
status=0;
for(k=0;k<num;k++)。
if(G[j][k]<maxright)。
status=1;
break;
if(status==0)
break;
do
printf("Please enter the vertex where Prim algorithm starts:");。
scanf("%d",&start);。
}while(start<0||start>num);。
in[start-1]=1;
for(i=0;i<num-1&&status;i++)。
for(j=0;j<num;j++)。
for(k=0;k<num;k++)。
if(G[j][k]<min&&in[j]&&(!in[k]))。
v1=j;
v2=k;
min=G[j][k];
if(!in[v2])
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=maxright;
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");。
else
for(i=0;i<num-1;i++)。
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);。
return 1;
}
Prim算法。
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)。
参考程序
//Prim 算法 读入顶点数(n)、边数(m)，边的起始点和权值 用邻接矩阵储存。
//例如
//7 12 (7个顶点12条边)。
//1 2 2
//1 4 1
//1 3 4
//2 4 3
//2 5 10
//3 4 2
//4 5 7
//3 6 5
//4 6 8
//4 7 4
//5 7 6
//6 7 1
#include <stdio.h>。
#include <string.h>。
int main()
int m , n;
int a[201][201] , mark[201] , pre[201] , dist[201];。
int s , t , w;
int i , j , k , min , tot;。
freopen("Prim.txt" , "r" , stdin);。
//读入数据
memset(a , 0 , sizeof(a));。
scanf("%d %d" , &n , &m);。
for (i = 0; i < m; i ++)。
scanf("%d %d %d" , &s , &t , &w);。
a[s][t] = w; a[t][s] = w;。
//赋初值
memset(mark , 0 , sizeof(mark));。
memset(pre , 0 , sizeof(pre));。
memset(dist , 9999 , sizeof(dist));。
dist[1] = 0;
//Prim
for (i = 1; i <= n; i ++)。
min = 9999; k = 0;。
for (j = 1; j <= n; j ++) 。
if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}。
if (k == 0) break;。
mark[k] = 1;
for (j = 1; j <= n; j ++)。
if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))。
dist[j] = a[k][j];。
pre[j] = k;
tot = 0;
for (i = 1; i <= n; i ++) tot += dist[i];。
printf("%d\n" , tot);。
return 0;
小韩在追星
数据结构 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ），利用K
第七章：
对于无向图，e的范围是：
数据结构中所讨论的图都是简单图，任意两结点间不会有双重的边。
对于有向图，e的范围是：
图的各种存储结构
邻接矩阵很方便访问任意两点的边，但是不方便计算其邻接点。在深度和广度遍历中广泛的需要求某点的邻接点。所以邻接矩阵只在Floyed和Prim和Dijstra中采用。
邻接表能很方便的求某顶点的邻接点，索引对于与遍历有关的算法大多都采用邻接表。如深度、广度、拓扑排序、关键路径。但他也有不足的地方，就是不方便求入度或是那些点可以到他的操作。所以有人引进逆邻接表。最后人们把这两种表结合到一起就是十字链表和邻接多重表。一个是存储有向图，另一个是存储无向图。
在十字链表和邻接多重表很方便求邻接点的操作和对应的逆操作。所以实际应用中，凡是能用邻接表实现的一定能用十字链表和邻接多重表实现。并且它们的存储效率更高。
1.邻接矩阵(有向图和无向图和网)又称为数组表示法。
typedef struct
{ vextype vexs[maxn]; ∥顶点存储空间∥。
adjtype A[maxn][maxn]; ∥邻接矩阵∥。
int vexnum,arcnum; //图的顶点数和边数。
GraphKind Kind; //图的类型。
} mgraph;
2.邻接表(有向图和无向图和网)。
typedef struct node ∥边。
{ int adj; int w; ∥邻接点、权∥。
struct node *next; ∥指向下一弧或边∥。
}linknode;
typedef struct ∥顶点类型∥。
{ vtype data; ∥顶点值域∥。
linknode *farc; ∥指向与本顶点关联的第一条弧或边∥。
}Vnode;
typedef struct
Vnode G[maxn]; ∥顶点表∥。
int vexnum,arcnum;。
GraphKind kind;。
}ALGraph;
adjvexnextarcinfo。
边结点
datafirstarc
顶点结点
3.十字链表(有向图和有向网)。
headvextaivexhlinktlinkinfo。
边结点
datafirstinfirstout。
顶点结点
4.邻接多重表(无向图)
markivexjvexilinkjlinkinfo。
边结点
datafirstedge
顶点结点
有向无环图(DAG)：是描述含有公共子式的表达式的有效工具。二叉树也能表示表达式，但是利用有向无环图可以实现对相同子式的共享，从而节省存储空间。
顶点的度：
无向图：某顶点V的度记为D(V)，代表与V相关联的边的条数。
有向图：顶点V的度D(V)=ID(V)+OD(V)。
强连通分量:在有向图中，若图中任意两顶点间都存在路径，则称其是强连通图。图中极大 强连通子图称之为强连通分量。
“极大”在这里指的是：往一个连通分量中再加入顶点和边，就构不成原图中的一个 连通子图，即连通分量是一个最大集的连通子图。有向图的连通就是指该有向图是。
强连通的
遍历图的过程实质上是_对每个顶点查找其邻接点的过程___ 其耗费的时间主要取决于采用的存储结构。当用邻接矩阵存储图时，查找每个顶点的邻接点所需的时间O( )，其中n是图中顶点数。而当用邻接表存储图时，找邻接点的所需时间为O(e)，其中e为图中边的个数或有向弧的个数，由此，当以邻接表作为存储结构时，深度优先搜索遍历图的时间复杂度O(n+e).。
广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者的不同之处仅在于对结点访问的顺序不同。也就是说他们的时间复杂度都取决于说采用的存储结构，当用邻接矩阵存储时，复杂度为O( )，当用邻接表存储时，时间复杂度为O(n+e).。
建图的算法：(邻接表是常考的，邻接矩阵简单，十字链表和 多重表和建邻接表十分的相似)。
void CreatGraph (AdjList &g) //建立有n个顶点和m 条边的无向图的邻接表存储结构。
{ int n,m;
scanf("%d%d",&n,&m);//输入顶点数和边数。
for (i =1,i<=n;i++)//输入顶点信息,建立顶点向量。
{ scanf(&g[i].vertex);。
g[i].firstarc=null;。
for (k=1;k<=m;k++)//输入边信息。
{ scanf(&v1,&v2);//输入两个顶点。
i= LocateVertex (g,v1); j=GraphLocateVertex (g,v2); //顶点定位。
p=(ArcNode *)malloc(sizeof(ArcNode));//申请边结点。
p->adjvex=j;。
p->next=g[i].firstarc; g[i].firstarc=p;//将边结点链入出边链表的头部。
p=(ArcNode *)malloc(sizeof(ArcNode)); //因为是无向图所以要在另外一个。
p->adjvex=i;。
p->next=g[j].firstarc; g[j].frstarc=p;// 顶点的出边表中插入该结点。
}//算法CreatGraph结束。
两种求最小生成树的算法(Prim和Kruskal)。
Prim算法中有双重循环，外层是求n-1条边内层是在closedge[v].lowcost 中求最小值和并列的求得当前加入点对closedge[]的影响。所以他的时间复杂度是O( )，它与途中边的数目没有关系，所以比较适合用在边比较稠密的图中。(顶点数相同，不管边数，都相同)。
Kruskal和他相对应，他的时间复杂度为O(eloge)，与图中的结点数目无关，至于边的个数有关。所以适合用在稀疏图中。(边数一定，不管顶点数，复杂度都相同)。
求最小生成树的普里姆(Prim)算法中边上的权不可以为负，
typedef struct {。
VertexType adjvex;。
VRType lowcost;。
}closedge[MAX_VERTEX_NUM];。
假设cost(u,w)表示边(u,w)上的权值，则对于集合 V-U 中每个顶点 w，
closedge[LocateVex(G, w)].lowcost = Min{cost(u,w)|u∈U}。
void MiniSpanTree_PRIM( MGraph G, VertexType u,SqList& MSTree)。
// G 为数组存储表示的连通网，按普里姆算法从顶点 u 出发构。
k = LocateVex ( G, u );。
for ( j=0; j
if (j!=k) closedge[j] = { u, G.arcs[k][j].adj };//{adjvex,lowcost}。
closedge[k].lowcost = 0; // 初始状态，U={u}。
for (i=1; i
{ k = minimum(closedge);// 求出T的下一个结点(图中第k顶点)。
// 此时closedge[k].lowcost =。
// Min{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U }。
printf(closedge[k].adkvex, G.vexs[k]); //输出生成编。
closedge[k].lowcost = 0; // 第 k 顶点并入U集。
for (j=0; j
if (G.arcs[k][j].adj < closedge[j].lowcost) //新顶点并入U后重新选最小边。
closedge[j] = { G.vexs[k], G.arcs[k][j].adj };。
} // for
} // MiniSpanTree。
拓扑排序问题
Status ToplogicalSort(ALGraph G)。
FindIndegree(G,indegree);//求各点的入度放在Indegree[vnum];。
InitStack(S);
for(i=0;i
if(Indegree[i]= =0)。
push(S,i);
count=0;
while(!StackEmpty(S))。
{ Pop(S,i); printf(i,G.vex[i].data); ++count;。
for(p=G..vex[i].firstarc; p; p=p->nextarc)。
{ k=p->adjvex;。
Indegree[k]--;
if( Indegree[k]= =0) push(S,k);。
}//for
}//while
if(count
return ERROR;
else
return OK
算法分析：求各顶点的入度的时间复杂度为O(e)，入度为零的点入栈O(n)，在循环中，每个顶点进一次栈，出栈一次，入度减1操作在while共执行了e次，所以总的时间复杂度为O(n+e).。
当图中无环时，也可以利用深度优先遍历进行拓扑排序，因为图中无环，所以最先退出DFS函数的顶点即出度为零的点，是拓扑排序中最后一个顶点。由此，按DFS函数的先后记录下来的顶点序列即为逆向的拓扑有序序列。
。
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：https://www.87dh.com/xl/。
小韩在追星
O(n^2), O(elog2e)。
求这两个结果的过程任何一本比较全面的数据结构教科书上都有的。