• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

最小生成树—普里姆算法(Prim算法)和克鲁斯卡尔算法(Kruskal算法)

OC/C/C++ 咸鱼的习惯 1752次浏览 0个评论

      最小生成树的性质:MST性质(假设N=(V,{E})是一个连通网,U是顶点集V的一个非空子集,如果(u,v)是一条具有最小权值的边,其中u属于U,v属于V-U,则必定存在一颗包含边(u,v)的最小生成树)

普里姆算法(Prim算法)

思路:以点为目标构建最小生成树
1.将初始点顶点u加入U中,初始化集合V-U中各顶点到初始顶点u的权值;
2.根据最小生成树的定义:从n个顶点中,找出 n – 1条连线,使得各边权值最小。循环n-1次如下操作:
      (1)从数组lowcost[k]中找到vk到集合U的最小权值边,并从数组arjvex[k] = j中找到该边在集合U中的顶点下标
      (2)打印此边,并将vk加入U中。
      (3)通过查找邻接矩阵Vk行的各个权值,即vk点到V-U中各顶点的权值,与lowcost的对应值进行比较,若更小则更新lowcost,并将k存入arjvex数组中

以下图为例
最小生成树---普里姆算法(Prim算法)和克鲁斯卡尔算法(Kruskal算法)

#include<bits/stdc++.h>
using namespace std;
#define MAXVEX 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
typedef struct {
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

void CreateMGraph(MGraph *G) {
	int m, n, w;	//vm-vn的权重w 	
	scanf("%d %d", &G->numVertexes, &G->numEdges);
	
	for(int i = 0; i < G->numVertexes; i++) {
		getchar();
		scanf("%c", &G->vexs[i]);
	}

	for(int i = 0; i < G->numVertexes; i++) {
		for(int j = 0; j < G->numVertexes; j++) {
			if(i == j)	G->arc[i][j] = 0;
			else	G->arc[i][j] = INF;
		}
	}		
	for(int k = 0; k < G->numEdges; k++) {
		scanf("%d %d %d", &m, &n, &w);
		G->arc[m][n] = w; 
		G->arc[n][m] = G->arc[m][n];
	}
}

void MiniSpanTree_Prim(MGraph G) {
	int min, j, k;
	int arjvex[MAXVEX];		//最小边在 U集合中的那个顶点的下标 
	int lowcost[MAXVEX];	// 最小边上的权值
	//初始化,从点 V0开始找最小生成树T 
	arjvex[0] = 0;		//arjvex[i] = j表示 V-U中集合中的 Vi点的最小边在U集合中的点为 Vj 
	lowcost[0] = 0;		//lowcost[i] = 0表示将点Vi纳入集合 U ,lowcost[i] = w表示 V-U中 Vi点到 U的最小权值 
	for(int i = 1; i < G.numVertexes; i++) {
		lowcost[i] = G.arc[0][i];
		arjvex[i] = 0;
	} 
	//根据最小生成树的定义:从n个顶点中,找出 n - 1条连线,使得各边权值最小
	for(int i = 1; i < G.numVertexes; i++) {
		min = INF, j = 1, k = 0;
		//寻找  V-U到 U的最小权值min 
		for(j; j < G.numVertexes; j++) {
			// lowcost[j] != 0保证顶点在 V-U中,用k记录此时的最小权值边在 V-U中顶点的下标 
			if(lowcost[j] != 0 && lowcost[j] < min) {
				min = lowcost[j];
				k = j;
			}
		}
	} 
	printf("V[%d]-V[%d] weight = %d\n", arjvex[k], k, min); 
	lowcost[k] = 0;		//表示将Vk纳入 U
	//查找邻接矩阵Vk行的各个权值,与lowcost的对应值进行比较,若更小则更新lowcost,并将k存入arjvex数组中
	for(int i = 1; i < G.numVertexes; i++) {
		if(lowcost[i] != 0 && G.arc[k][i] < lowcost[i]) {
			lowcost[i] = G.arc[k][i];
			arjvex[i] = k;
		}
	} 
	
}

int main() {
	MGraph *G = (MGraph *)malloc(sizeof(MGraph));
	CreateMGraph(G);
	MiniSpanTree_Prim(*G);
} 
 
/*
input:
	4 5	
	a
	b
	c
	d
	0 1 2
	0 2 2
	0 3 7
	1 2 4
	2 3 8

output:
	V[0]-V[1] weight = 2
	V[0]-V[2] weight = 2
	V[0]-V[3] weight = 7
	最小总权值: 11
*/

时间复杂度O(n^2)

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

思路:以边为目标进行构建最小生成树
      在边集中依次寻找最小权值边,若构建是不形成环路(利用parent数组记录各点的连通分量),则将其添加到最小生成树中。
判断是否形成环路思路:
      初始化parent数组为各个顶点的下标,以此表示每个顶点为不同的连通分量,寻找最小权值边时,判断该边起点和终点是否属于同一连通分量,如果不属于则将该边加入最小生成树中,并将该边的起点和终点的连通分量更改为已形成的最小生成树起始点的连通分量。

#include<bits/stdc++.h>
using namespace std;
#define MAXVEX 100
#define MAXEDGE 100
#define INF 65535
typedef char VertexType;
typedef int EdgeType;
//图的邻接矩阵存储结构的定义 
typedef struct {
	VertexType vexs[MAXVEX];
	EdgeType arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;

//边集数组Edge结构的定义 
typedef struct {
	int begin;
	int end;
	int weight;
}Edge;

bool vis[100][100];

void CreateMGraph(MGraph *G) {
	int m, n, w;	//vm-vn的权重w 	
	scanf("%d %d", &G->numVertexes, &G->numEdges);
	
	for(int i = 0; i < G->numVertexes; i++) {
		getchar();
		scanf("%c", &G->vexs[i]);
	}

	for(int i = 0; i < G->numVertexes; i++) {
		for(int j = 0; j < G->numVertexes; j++) {
			if(i == j)	G->arc[i][j] = 0;
			else	G->arc[i][j] = INF;
		}
	}		
	for(int k = 0; k < G->numEdges; k++) {
		scanf("%d %d %d", &m, &n, &w);
		G->arc[m][n] = w; 
		G->arc[n][m] = G->arc[m][n];
	}
}

void MiniSpanTree_Kruskal(MGraph G) {
	int v1, v2, vs1, vs2;
	Edge edges[MAXEDGE];
	int parent[MAXVEX]; //标记各顶点所属的连通分量,用于判断边与边是否形成环路 
	
	//将邻接矩阵转换成按权值从小到大排序的边集数组 
	/*
	
	*/	
	int tmp = 0, m, n, ans;
	ans = (G.numVertexes*G.numVertexes) / 2 - G.numVertexes / 2;	
	for(int k = 0; k < ans; k++) {
		int min = INF, i, j;
		for(i = 0; i < G.numVertexes; i++) {
			for(j = 0; j < G.numVertexes; j++) {
				if(!vis[i][j] && i < j && min > G.arc[i][j]) {
					min = G.arc[i][j];
					m = i;
					n = j;			
				}
			}
		}	
		if(G.arc[i][j] == INF)
			continue;			
		edges[tmp].begin = m;
		edges[tmp].end = n;
		edges[tmp].weight = min;
		vis[m][n] = true;
		tmp++;	
	}	
	 
	
	//初始化为各顶点各自为一个连通分量 
	for(int i = 0; i < G.numVertexes; i++)
		parent[i] = i;
		
	for(int i = 0; i < G.numEdges; i++) {
		//起点终点下标 
		v1 = edges[i].begin;
		v2 = edges[i].end;
		//起点终点连通分量 
		vs1 = parent[v1];
		vs2 = parent[v2];
		//边的两个顶点属于不同的连通分量,打印,将新来的连通分量更改为起始点的连通分量 
		if(vs1 != vs2) {
			printf("V[%d]-V[%d] weight:%d\n", edges[i].begin, edges[i].end, edges[i].weight);
			for(int j = 0; j < G.numVertexes; j++) {
				if(parent[j] == vs2)	parent[j] = vs1;
			}
		}
	} 
}

int main() {
	MGraph *G = (MGraph *)malloc(sizeof(MGraph));
	CreateMGraph(G);
	MiniSpanTree_Kruskal(*G);
} 

/*
input:
	4 5	
	a
	b
	c
	d
	0 1 2
	0 2 2
	0 3 7
	1 2 4
	2 3 8

output:
	V[0]-V[1] weight:2
	V[0]-V[2] weight:2
	V[0]-V[3] weight:7

*/

时间复杂度O(elog2e) e为边数


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明最小生成树—普里姆算法(Prim算法)和克鲁斯卡尔算法(Kruskal算法)
喜欢 (0)

您必须 登录 才能发表评论!

加载中……