两种最小生成树的方法——普里姆算法、克鲁斯卡尔算法_最小生成树两种算法

目录

一、最小生成树的概念

二、MST性质

1、性质

2、 证明

二、普里姆(Prim)算法

1、算法思想

2、图形解析

3、逐步实现

（1）建立无向图的邻接矩阵

（2）找出辅助数组中与closedge代价最小的顶点的位置

（3）普里姆核心算法

4、总代码

5、时间复杂度

三、克鲁斯卡尔(Kruskal)算法

1、算法思想

2、图形解析

3、逐步实现

（1）构建无向图的邻接表

（2）找到可连接的边

（3）判断最小生成树是否完成

（4）克鲁斯卡尔核心算法

4、总代码

5、时间复杂度

---

一、最小生成树的概念

在连通网的所有生成树中，所有边的代价和最小的生成树。

二、MST性质

       构建最小生成树的算法有多种，比如普里姆算法、克鲁斯卡尔算法。其中多数算法利用了最小生成树的下列一种简称MST的性质。 

1、性质

       假设N=( V , { E } )是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一颗包含边（u，v）的最小生成树。

                    图1  连通图N 

2、 证明

利用反证法证明。

      假设网N的任意一颗最小生成树都不包含（u，v）。

      设T是连通网上的一颗最小生成树。

      当将边（u，v）加入到T中时，由生成树的定义，T中必存在一条包含（u，v）的回路。另一方面，由于T是生成树，则在T上必存在另一条边（u’，v’），其中u’∈U，v’∈V-U，且u和u’之间，v和v’之间均有路径相通。删去边（u’，v’），便可消除上述回路，同时得到另一颗生成树T’。因为（u，v）的代价不高于（u’，v’），则T’的代价也不高于T，T’是包含（u，v）的一颗最小生成树。

      由此与假设矛盾，性质正确。

                               

                 图2  假设的最小生成树T                                           图3  实际的最小生成树T ’

二、普里姆(Prim)算法

1、算法思想

(1)设G=(V，E)是连通图，TE是N上最小生成树中边的集合。

(2)初始令U={u0}，(u0∈V)，TE={ }。

(3)在所有u∈U，v∈V-U的边（u，v）∈E中，找一条代价最小的边（u0，v0）。

(4)将（u0，v0）并入集合TE，同时v0并入U。

(5)重复上述操作直至U=V为止，则T=（V，TE）为N的最小生成树。

2、图形解析

                                               图4  普里姆算法的图解 

3、逐步实现

（1）建立无向图的邻接矩阵

int CreateGraph(MGraph& G) {
	//创建无向网的邻接矩阵 
	int v1,v2,w;  //邻接两点v1，v2,以及所构成边的权值w 
	printf("请输入顶点数和边数：");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	for (int i = 0; i < G.vexnum; ++i){ 
		//构造顶点向量 
		printf("请输入第%d个顶点的值：",i+1);
		scanf("%d", &G.vexs[i]);
	}
	for (int i = 0; i < G.vexnum; ++i){
		//初始化邻接矩阵， 将各边的权值都赋值为 INT_MAX
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j]=  INFINITY ;
	}
	for (int k = 0; k < G.arcnum; ++k) {
		//构造邻接矩阵 
		printf("请输入相邻两点的值，以及他们所构成边的权值：");
		scanf("%d%d%d", &v1, &v2, &w);
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);
		G.arcs[i][j]= w;
		G.arcs[j][i] = G.arcs[i][j];  //无向网邻接矩阵对称 
	}
	return 0;
}

（2）找出辅助数组中与closedge代价最小的顶点的位置

int minimum(struct closedge[], int n){ 
    //找出辅助数组中与closedge代价最小的顶点的位置
    int i = 0, j, min, k;
    while (!closedge[i].lowcost)  //由于初始设lowcost都为0，所以从第一个不为零的值开始
        i++;
    min = closedge[i].lowcost;
    k = i;
    for (j = 1; j < n; j++)  //依次遍历、比较，最后输出最小值
        if (closedge[j].lowcost)
            if (min > closedge[j].lowcost){
                min = closedge[j].lowcost;
                k = j;
            }
    return k;
}

（3）普里姆核心算法

（此处使用伪代码）

void MiniSpanTree_Prim(MGraph  G,VertexType u){     
//用普里姆算法从第u个顶点出发构造网G的最小生成树T
      k = LocateNode(G,u);
      for(j = 0;j<G.vexnum;++j)     //辅助数组初始化
            if(j!=k)   closedge[j] = {u,G.arcs[k][j].adj};     //{adjvex,lowcost}
      closedge[k].lowcost = 0;    //初始，U={u}
      for(i=1;i<G.vexnum;++i){    //选择其余G.vexnum – 1个顶点
            k = minimum(closedge);     //求出T的下一个结点，第k个顶点
            printf(closedge[k].adjvex,G.vexs[k]);    //输出生成树的边
            closedge[k].lowcost = 0;    //第k个顶点并入U集
            for(j=0;j<G.vexnum;++j)
                  if(G.arcs[k][j].adj<closedge[j].lowcost)      //新顶点并入U后重新选择最小边
                        closedge[j] = {G.vexs[k],G.arcs[k][j].adj};
       }
}  //MiniSpanTree_Prim

4、总代码

#include<stdio.h>
#include<limits.h>
 
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
 
typedef struct {
	int vexs[MAX_VERTEX_NUM];  //顶点向量 
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  //邻接矩阵 
	int vexnum, arcnum;  //顶点数，边数 
}MGraph;
 
//记录从顶点集U到V-U的代价最小的边的辅助数组定义 
struct closedge{
	int adjvex;  //顶点
	int lowcost;  //其他顶点与adjvex顶点相连的边的权值 
}closedge[MAX_VERTEX_NUM];
 
int LocateVex(MGraph G,int v) {
	//顶点v在网G中的位序 
	for (int i = 0; i < G.vexnum; ++i) {
		if (v == G.vexs[i])
			return i;
	}
	return -1;
}
 
int CreateGraph(MGraph& G) {
	//创建无向网的邻接矩阵 
	int v1,v2,w;  //邻接两点v1，v2,以及所构成边的权值w 
	printf("请输入顶点数和边数：");
	scanf("%d%d", &G.vexnum, &G.arcnum);
	for (int i = 0; i < G.vexnum; ++i){ 
		//构造顶点向量 
		printf("请输入第%d个顶点的值：",i+1);
		scanf("%d", &G.vexs[i]);
	}
	for (int i = 0; i < G.vexnum; ++i){
		//初始化邻接矩阵， 将各边的权值都赋值为 INT_MAX
		for (int j = 0; j < G.vexnum; ++j)
			G.arcs[i][j]=  INFINITY ;
	}
	for (int k = 0; k < G.arcnum; ++k) {
		//构造邻接矩阵 
		printf("请输入相邻两点的值，以及他们所构成边的权值：");
		scanf("%d%d%d", &v1, &v2, &w);
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2);
		G.arcs[i][j]= w;
		G.arcs[j][i] = G.arcs[i][j];  //无向网邻接矩阵对称 
	}
	return 0;
}
 
void PrintG(MGraph G) {
	//打印邻接矩阵 
	printf("邻接矩阵为：\n");
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[i][j]== INFINITY)
            	//对于权值为INT_MAX的边，输出 ∞
                printf("∞\t");
            else
            	printf("%d\t",G.arcs[i][j]);
        }
        printf("\n");
    }
}
 
int minimum(struct closedge[], int n){ 
    //找出辅助数组中与closedge代价最小的顶点的位置
    int i = 0, j, min, k;
    while (!closedge[i].lowcost)
        i++;
    min = closedge[i].lowcost;
    k = i;
    for (j = 1; j < n; j++)
        if (closedge[j].lowcost)
            if (min > closedge[j].lowcost)
            {
                min = closedge[j].lowcost;
                k = j;
            }
    return k;
}
 
void MiniSpanTree_PRIM(MGraph G,int u){
	//普里姆算法求最小生成树 ，从顶点u出发构造最小生成树
	int k = LocateVex(G,u);
	for(int j= 0;j<G.vexnum;++j)
	//初始化辅助数组 
		if(j!= k){
			closedge[j].adjvex = u;
			closedge[j].lowcost = G.arcs[k][j];
		}
	closedge[k].lowcost = 0;  //初始，U={u} 
	printf("最小生成树为：\n");
	for(int i =1;i<G.vexnum;++i){
		//选择其余G.vexnum-1个顶点 
		k = minimum(closedge,G.vexnum);  //找出与u代价最小的邻接点 
		printf("V%d----V%d", LocateVex(G,closedge[k].adjvex) + 1, k + 1);
		printf(" = %d\n",G.arcs[LocateVex(G,closedge[k].adjvex)][k]);
		closedge[k].lowcost = 0;  //第k个顶点并入U
		for(int j = 0;j<G.vexnum;++j)
			if(G.arcs[k][j]< closedge[j].lowcost){
				//新顶点并入U后重新选择最小值 
				closedge[j].adjvex = G.vexs[k];
				closedge[j].lowcost = G.arcs[k][j];
			}
	}
}
 
int main(){
	MGraph G;
	CreateGraph(G);
	PrintG(G);
	MiniSpanTree_PRIM(G,1);
	return 0;
}

5、时间复杂度

普里姆算法的性能取决于如何选取下一条最小权值的边

时间复杂度为O(n^2)

与网中的边数无关

因此适用于求边稠密的网的最小生成树

三、克鲁斯卡尔(Kruskal)算法

1、算法思想

(1)设连通网G=(V，E)，令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V，{ })，每个顶点自成一个连通分量。

(2)在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入的T中；否则，舍去此边，选取下一条代价最小的边。

(3)依次类推，直到T中所有顶点都在同一连通分量上为止。

2、图形解析

                                                  图5   克鲁斯卡尔算法的图解 

3、逐步实现

（1）构建无向图的邻接表

int CreateGraph(ALGraph &G){
	//创建无向网的邻接表 
	printf("输入图的顶点数和边数：");
	scanf("%d%d",&G.vexsnum,&G.arcsnum);
	G.p = (Edge*)malloc(sizeof(Edge)*(G.arcsnum + 1));  //分配G.arcsnum + 1个空间，多分配出1个空间 
	G.m = (int*)malloc(sizeof(int)*(G.vexsnum));  //分配G.vexsnum个空间 
	for(int i = 0;i<G.vexsnum;++i){
		printf("请输入第%d个顶点值",i+1);
		scanf("%d",&G.m[i]);
	}
	for(int i = 0;i<G.arcsnum;++i){
		printf("请输入邻接两点以及所构成的边的权值：");
		scanf("%d%d%d",&G.p[i].v1,&G.p[i].v2,&G.p[i].weight);
	}
	for(int i = 0;i<G.arcsnum;++i){
	//使用冒泡排序将权重从小到大存到边集数组里 
		for(int j = G.arcsnum-1;j>i;--j){
			if(G.p[i].weight>G.p[j].weight){
				G.p[G.arcsnum] = G.p[i];  //暂时将大的权值赋值到多出来的那个空间 
				G.p[i] = G.p[j];
				G.p[j] = G.p[G.arcsnum];
			}
		}
	}
	return 0;
}

（2）找到可连接的边

此处用到并查集的算法

int Find(int *parent,int g){
	//通过parent[]找到可连接的边
	while(parent[g]!=0){
	//利用循环找到g的根 
		g = parent[g]; 
	}
	return g;
}

（3）判断最小生成树是否完成

int IsFinish(ALGraph &G,int *parent){
	//判断生成树是否完成，完成的标志是生成树的边等于顶点的数量减1
	int i,n = 0;
	for(i = 0;i<G.vexsnum;++i){
		if(parent[i]) n++;
	}
	if(n == G.vexsnum-1) return 1;	//如果等于就表示最小树生成结束 
	return 0;
}

（4）克鲁斯卡尔核心算法

（此处使用伪代码）

int MiniSpanTree_Kruskal(ALGraph &G){        
//用克鲁斯卡尔算法构造网G的最小生成树T
    int parent[G.vexsnum];       //辅助数组，用于判断两个点是否在同一个连通分量中
    for(int i = 0;i<G.vexsnum;++i)       //初始化辅助数组
        parent[i] = 0;
    for(int i = 0;i<G.arcsnum;++i){
        a=Find(parent,LocateVex(G,G.p[i].v1));  //找到v1、v2的根a、b
        b=Find(parent,LocateVex(G,G.p[i].v2));
        if(a != b){    //判断是否成环，如果a==b则表是v1和v2在同一颗生成树上
	        parent[a] = b；   //不在同一棵树上，合并为同一棵树
	        printf(G.p[i].v1,G.p[i].v2,G.p[i].weight);     //输出生成树的边
        }
	if(IsFinish(G,parent))   //判断是否完成，完成的标志是生成树的边等于顶点的数量减1
        return 0 ;  
       }
}   //MiniSpanTree_Kruskal

4、总代码

#include<stdio.h>
#include<stdlib.h> 
 
typedef struct Edge{
	int v1;
	int v2;
	int weight;
}Edge;
typedef struct ALGraph{
	int vexsnum;  //顶点数 
	int arcsnum;  //边数 
	Edge *p;  //指针p指向边集数组 
	int *m;  //指针m指向顶点集数组 
}ALGraph;
 
int CreateGraph(ALGraph &G){
	//创建无向网的邻接表 
	printf("输入图的顶点数和边数：");
	scanf("%d%d",&G.vexsnum,&G.arcsnum);
	G.p = (Edge*)malloc(sizeof(Edge)*(G.arcsnum + 1)); //分配G.arcsnum + 1个空间，多分配出1个空间 
	G.m = (int*)malloc(sizeof(int)*(G.vexsnum));  //分配G.vexsnum个空间 
	for(int i = 0;i<G.vexsnum;++i){
		printf("请输入第%d个顶点值",i+1);
		scanf("%d",&G.m[i]);
	}
	for(int i = 0;i<G.arcsnum;++i){
		printf("请输入邻接两点以及所构成的边的权值：");
		scanf("%d%d%d",&G.p[i].v1,&G.p[i].v2,&G.p[i].weight);
	}
	for(int i = 0;i<G.arcsnum;++i){
	//使用冒泡排序将权重从小到大存到边集数组里 
		for(int j = G.arcsnum-1;j>i;--j){
			if(G.p[i].weight>G.p[j].weight){
				G.p[G.arcsnum] = G.p[i];  //暂时将大的权值赋值到多出来的那个空间 
				G.p[i] = G.p[j];
				G.p[j] = G.p[G.arcsnum];
			}
		}
	}
	return 0;
}
 
int Find(int *parent,int g){
	//通过parent[]找到可连接的边
	while(parent[g]!=0){
	//利用循环找到g的根 
		g = parent[g]; 
	}
	return g;
}
 
int IsFinish(ALGraph &G,int *parent){
	//判断生成树是否完成，完成的标志是生成树的边等于顶点的数量减1
	int i,n = 0;
	for(i = 0;i<G.vexsnum;++i){
		if(parent[i]) n++;
	}
	if(n == G.vexsnum-1) return 1;	//如果等于就表示最小树生成结束 
	return 0;
}
 
int LocateVex(ALGraph &G,int g){
	//找到顶点的下标
	int i;
	for(i = 0;i<G.vexsnum;++i){
		if(G.m[i] == g)
			return i;
	}
	return -1;
}
 
int MiniSpanTree_Kruskal(ALGraph &G){
	int a,b;
	int parent[G.vexsnum];  //辅助数组，判断两个点是否在同一个连通分量中 
	for(int i = 0;i<G.vexsnum;++i){
	//初始化parent[]，全部赋值为0 
		parent[i] = 0;
	}
	printf("最小生成树为：\n");
	for(int i = 0;i<G.arcsnum;++i){
		a = Find(parent,LocateVex(G,G.p[i].v1));  //找到v1、v2的根a、b 
		b = Find(parent,LocateVex(G,G.p[i].v2));
		
		if(a != b){
		//判断是否成环，如果a==b则表是v1和v2在同一颗生成树上，如果a和b连接则为生成环，不符合生成树
			parent[a] = b;  //不在一棵树上，合并为在同一棵树上 
			printf("V%d----V%d = %d\n",LocateVex(G,G.p[i].v1),LocateVex(G,G.p[i].v2),G.p[i].weight);
		} 
		if(IsFinish(G,parent))
		//判断是否完成，完成后返回 
			return 0 ;
	}
}
 
int main(){
	ALGraph G;
	CreateGraph(G);
	MiniSpanTree_Kruskal(G);
	return 0;
}

5、时间复杂度

克鲁斯卡尔算法时间复杂度主要取决于将权值边按从小到大的顺序排列

时间复杂度为O(eloge)

e为网中边的数目

因此适用于求边稀疏的网的最小生成树。