MST在前面学习了Kruskal算法，还有一种算法叫做Prim的。这两者的区别是Prim算法适合稠密图，比如说鸟巢这种几乎所有点都有相连的图。其时间复杂度为O(n^2)，其时间复杂度与边的数目无关；而kruskal算法的时间复杂度为O(eloge)，跟边的数目有关，适合稀疏图。

 

prim算法

  基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V），TE＝{ 空集 }开始。重复执行下列操作：

   1.在所有u∈U，v∈V-U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止；接下里以 v0为边的起点，继续寻找权值最小的边并入集合TE中，依次往复；

   2.最后，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

   Prim算法的核心：始终保持TE中的边集构成一棵生成树，也就是它与Kruskal算法的主要区别是，Prim是一直保持一种串联的状态而不遵从整体的贪心算法。其实初始点uo的选择可以随意，一般做题题目条件会给出或者取最小的权值边。

其实现的代码如下：

 

#include 
    
     #include 
     
      #include 
      
     
    

#define infinity 1000000#define max_vertexes 6

typedef int Graph[max_vertexes][max_vertexes];

void prim(Graph G,int vcount,int father[]){    int i,j,k; int lowcost[max_vertexes];int closeset[max_vertexes],used[max_vertexes];int min;  for (i=0;i

邻接矩阵的形式进行存储的实现：

 

 

#include 
    
     #define n 6#define MaxNum 10000  /*定义一个最大整数*//*定义邻接矩阵类型*/typedef int adjmatrix[n+1][n+1];   /*0号单元没用*/typedef struct{	int fromvex,tovex;	int weight;}Edge;typedef Edge *EdgeNode;int arcnum;     /*边的个数*//*建立图的邻接矩阵*/void CreatMatrix(adjmatrix GA){	int i,j,k,e;	printf("图中有%d个顶点\n",n);	for(i=1;i<=n;i++){		for(j=1;j<=n;j++){			if(i==j){				GA[i][j]=0;         /*对角线的值置为0*/			}			else{				GA[i][j]=MaxNum;    /*其它位置的值置初始化为一个最大整数*/			}		}	}	printf("请输入边的个数：");	scanf("%d",&arcnum);	printf("请输入边的信息，按照起点，终点，权值的形式输入：\n");	for(k=1;k<=arcnum;k++){		scanf("%d,%d,%d",&i,&j,&e);  /*读入边的信息*/		GA[i][j]=e;		GA[j][i]=e;	}}/*初始化图的边集数组*/void InitEdge(EdgeNode GE,int m){	int i;	for(i=1;i<=m;i++){		GE[i].weight=0;	}}/*根据图的邻接矩阵生成图的边集数组*/void GetEdgeSet(adjmatrix GA,EdgeNode GE){	int i,j,k=1;	for(i=1;i<=n;i++){		for(j=i+1;j<=n;j++){			if(GA[i][j]!=0&&GA[i][j]!=MaxNum){				GE[k].fromvex=i;				GE[k].tovex=j;				GE[k].weight=GA[i][j];				k++;			}		}	}}/*按升序排列图的边集数组*/void SortEdge(EdgeNode GE,int m){	int i,j,k;	Edge temp;	for(i=1;i
     
      GE[j].weight){				k=j;			}		}		if(k!=i){			temp=GE[i];GE[i]=GE[k];GE[k]=temp;		}	}}/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/void Prim(adjmatrix GA,EdgeNode T){	int i,j,k,min,u,m,w;	Edge temp;	/*给T赋初值，对应为v1依次到其余各顶点的边*/	k=1;	for(i=1;i<=n;i++){		if(i!=1){			T[k].fromvex=1;			T[k].tovex=i;			T[k].weight=GA[1][i];			k++;		}	}	/*进行n-1次循环，每次求出最小生成树中的第k条边*/	for(k=1;k