最小生成树——Prim、Kruskal
本文最后更新于10 天前,其中的信息可能已经过时,如有错误请发送邮件到big_fw@foxmail.com

借助生成树,可以解决实际生活中的很多问题。

例如,为了方便 6 座城市中居民的生产和生活,政府要在 6 座城市之间修建公路。本着节约资金的原则,6 座城市只需要建立 5 条公路即可实现连通,如何修建公路才能最大程度上节省资金呢?

最小生成树:构造连通网的最小代价生成树。

1.普里姆(Prim)算法

普里姆算法查找最小生成树的过程,采用了贪心算法的思想。

对于包含 N 个顶点的连通网,普里姆算法每次从连通网中找出一个权值最小的边,这样的操作重复 N-1 次,由 N-1 条权值最小的边组成的生成树就是最小生成树。

下面是普里姆算法实现过程:

关于普里姆(Prim)算法代码实现:

#include<iostream>
using namespace std;


#define MAXVEX 20
#define GRAPH_INFINITY 65535


typedef struct {
	int arc[MAXVEX][MAXVEX];//邻接矩阵
	int numNodes;//顶点数
	int numEdges;//边数 
}MGraph; 


//构建图 
void CreateMGraph(MGraph *G){
	
	int i,j;
	
	G->numNodes = 6;
	G->numEdges = 9;
	
	//初始化邻接矩阵
	for(i = 0; i < G->numNodes; i++){
		for(j = 0;j < G->numNodes; j++){
			if(i==j){
				G->arc[i][j] = 0;
			}else{
				G->arc[i][j] = G->arc[j][i] = GRAPH_INFINITY;;
			}
		}
	} 
	
	G->arc[0][1] = 6;
	G->arc[0][2] = 3;
	G->arc[0][4] = 7;
	G->arc[1][2] = 4;
	G->arc[1][3] = 2;
	G->arc[1][5] = 5;
	G->arc[2][3] = 3;
	G->arc[2][4] = 8;
	G->arc[3][5] = 2; 
	
	
	for(i = 0; i < G->numNodes; i++)
	{
		for(j = i; j < G->numNodes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}
}


//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G){
	int min,i,j,k;
	int adjvex[MAXVEX];	//保存相关顶点的权值下标
	int lowcost[MAXVEX];	//保存相关顶点间的边的权值
	lowcost[0] = 0;	//初始化第一个权值为0,即v0加入生成树 
	adjvex[0] = 0;//初始化第一个顶点下标为0
	
	//这里注意因为之前已经存入一个,所以从1开始 
	for(i = 1;i < G.numNodes; i++){
		lowcost[i] = G.arc[0][i];	//将v0顶点与之有边的权值存入数组 
		adjvex[i] = 0;	//初始化都为v0的下标 
	} 
	
	for(i = 1; i < G.numNodes; i++){
		//初始化最小权值,可以为65535
		min = 65535;
		j = 1;
		k = 0;
		
		while(j < G.numNodes){
			//如果权值不为0且权值小于min 
			if(lowcost[j] != 0 && lowcost[j] < min){
				min = lowcost[j];
				k = j;
			}
			j++;
		} 
		
		cout<<"("<<adjvex[k]<<","<<k<<")"<<endl;//打印当前顶点中权值最小的边
		lowcost[k] = 0; //将当前顶点权值设置为0,此i的那个点已完成任务
		
		for(j = 1; j < G.numNodes; j++){
			//如果下标为k的顶点的各边权值小于此前这些顶点未被加入生成树的权值 
			if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
				lowcost[j] = G.arc[k][j];//将较小的权值存入lowcost相应未知 
				adjvex[j] = k;//将下标为k的顶点存入adjvex 
			}
		} 
		
	} 
	 
	
} 
int main()
{
	MGraph G;
	CreateMGraph(&G);
	cout<<"最小生成树:"<<endl; 
	MiniSpanTree_Prim(G);
  
	return 0;
 
}

2.克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔算法查找最小生成树的方法是:将连通网中所有的边按照权值大小做升序排序,从权值最小的边开始选择,只要此边不和已选择的边一起构成环路,就可以选择它组成最小生成树。对于 N 个顶点的连通网,挑选出 N-1 条符合条件的边,这些边组成的生成树就是最小生成树。

下面是克鲁斯卡尔算法实现过程:

首先我们需要将连通图中边按照权值大小进行排序:

A : 0 , B : 1 , C : 2 , D : 3 , S : 4 , T : 5;

beginendweight
Edges[0]132
Edges[1]352
Edges[2]023
Edges[3]233
Edges[4]214
Edges[5]155
Edges[6]016
Edges[7]407
Edges[8]428

生成的最小生成树如下面所示:

关于克鲁斯卡尔(Kruskal)算法代码实现:

#include<iostream>
using namespace std;

#define MAXVEX 20
#define MAXEDGE 20

typedef struct {
	int arc[MAXVEX][MAXVEX];
	int numNodes;//顶点数 
	int numEdges;//边数 
}MGraph;

typedef struct {
	int begin;
	int end;
	int weight;//权值 
}Edge;


void CreateMGraph(MGraph *G){
	int i,j;
	
	G->numNodes = 6;
	G->numEdges = 9;
	
	//初始化邻接矩阵
	for(i = 0; i < G->numNodes; i++){
		for(j = 0;j < G->numNodes; j++){
			if(i==j){
				G->arc[i][j] = 0;
			}else{
				G->arc[i][j] = G->arc[j][i] = 65535;
			}
		}
	} 
	
	G->arc[0][1] = 6;
	G->arc[0][2] = 3;
	G->arc[0][4] = 7;
	G->arc[1][2] = 4;
	G->arc[1][3] = 2;
	G->arc[1][5] = 5;
	G->arc[2][3] = 3;
	G->arc[2][4] = 8;
	G->arc[3][5] = 2; 
	
	
	for(i = 0; i < G->numNodes; i++)
	{
		for(j = i; j < G->numNodes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}
} 


//查找连线顶点的尾部下标
int Find(int *parent,int f){
	while(parent[f] > 0){
		f = parent[f];
	}
	return f;
} 


//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G){
	int i,j,n,m;
	Edge edges[MAXEDGE];//边集数组 
	int parent[MAXVEX]; //定义一数组用来判断边是否形成回路
	
	//此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排序代码
	edges[0].begin = 0;
	edges[0].end = 1;
	edges[0].weight = 6;
	
	edges[1].begin = 0;
	edges[1].end = 2;
	edges[1].weight = 3;
	
	edges[2].begin = 0;
	edges[2].end = 4;
	edges[2].weight = 7;
	
	edges[3].begin = 1;
	edges[3].end = 2;
	edges[3].weight = 4;
	
	edges[4].begin = 1;
	edges[4].end = 3;
	edges[4].weight = 2;
	
	edges[5].begin = 1;
	edges[5].end = 5;
	edges[5].weight =5;
	
	edges[6].begin = 2;
	edges[6].end = 3;
	edges[6].weight = 3;
	
	edges[7].begin = 2;
	edges[7].end = 4;
	edges[7].weight = 8;
	
	edges[8].begin = 3;
	edges[8].end = 5;
	edges[8].weight = 2;
	
	Edge edge;
	
	for(i = 0;i < G.numEdges;i++){
		for(j = 0;j < G.numEdges-1-i;j++){
			if(edges[j].weight > edges[j+1].weight){
				edge = edges[j];
				edges[j] = edges[j+1];
				edges[j+1] = edge;
			}
		}
	} 
	
		
	for(i = 0; i < G.numNodes; i++){
		parent[i] = 0;//初始化数组值为0 
	} 
	//循环每一条边 
	for(i = 0;i < G.numEdges; i++){
		n = Find(parent,edges[i].begin);
		m = Find(parent,edges[i].end);
		
		//假如n不等于m,说明此边没有与现有的生成树形成回路 
		if(n != m){
			//将此边的结尾顶点放入下标为起点的parent中,表示此顶点已经在生成树的集合中
			parent[n] = m;
			cout<<"("<<edges[i].begin<<","<<edges[i].end<<")"<<" "<<edges[i].weight<<endl; 
		} 
	} 
	 
} 


int main()
{
	MGraph G;
	CreateMGraph(&G);
	MiniSpanTree_Kruskal(G);
	return 0;
}
如果觉得本文对您有所帮助,可以支持下博主,一分也是缘
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇