图的最小生成树--Prim算法与Kruskal算法

2022/1/3 9:38:44

本文主要是介绍图的最小生成树--Prim算法与Kruskal算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 相关概念

1.1 生成树概念

所谓一个图的生成树是一个极小连通子图,它含有图中全部的n个顶点,但只有足以构成一棵树的n-1条边。
从上述定义可知,如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多余n-1条边,必定构成一个环。
注意:
(1)一个图可以有多棵不同的生成树;
(2)具有n-1条边并不一定是生成树。

1.2 最小生成树

给定一个连通网,在该往的所有生成树中,使得各边权值之和最小的那棵生成树称为该网的最小生成树(Minimum Spanning Tree, MST),也叫最小代价生成树。
注意:当网中有多个相同权值的边时,最小生成树可能不唯一

1.3 MST性质

构造最小生成树的多数算法都利用了MST的性质。
MST性质:设N=(N,E)是一个连通网,U是顶点集V的一个非空子集。若边(u, v)是一条具有最小权值的边,其中u∈U,v属于V-U,则必存在一棵包含边(u,v)的最小生成树。
MST性质解释:在生成树的构造过程中,图中n个顶点分属两个集合:
U:已落在生成树上的顶点集;
V-U:尚未落在生成树上的顶点集 。
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

2. 普里姆(Prim)算法

算法思想:
设N=(V,E)是连通网,TE是N上最小生成树中边的集合;
初始令U={u0}(u0∈V),TE={};
在所有u∈U,v∈V-U的边(u, v)∈E中找一条代价最小的边(u0,v0);
将(u0,v0)并入集合TE,同时v0并入U;
重复上述操作直至U=V为止,则T=(V, {TE})为N的最小生成树。

Prim算法是以某顶点为起点,逐步找各顶点上最小权值的边来构造最小生成树的,算法时间复杂度为O(n^2)

#include <iostream>
using namespace std;

/**************************************************************************************
*********************************** 图结构定义及操作 ***********************************
***************************************************************************************/
typedef char VertexType;	// 顶点类型,自定义
typedef int  WeightType;	// 边上权值类型,自定义

#define MAXVEX		(100)	// 最大顶点数
#define INFINITY	(65535)	// 用65535表示∞,表示顶点之间没有边

typedef struct {
	VertexType vexs[MAXVEX];			// 顶点数组
	WeightType arcs[MAXVEX][MAXVEX];	// 邻接矩阵
	int Nv, Ne;							// 顶点数、边数
} MGraph;

/**
* @brief:	建立图的邻接矩阵结构
* @param G:指向图的指针
* @return:	void
*/
void createMGraph(MGraph* G) {
	cout << "输入顶点数和边数:";
	cin >> G->Nv >> G->Ne;

	// 初始化邻接矩阵
	for (int i = 0; i < G->Nv; i++)
	{
		for (int j = 0; j < G->Nv; j++)
		{
			G->arcs[i][j] = (i == j) ? 0 : INFINITY;	// 邻接矩阵主对角线初始化为0,其余初始化为INFINITY
		}
	}

	cout << "输入顶点信息:";
	for (int i = 0; i < G->Nv; i++)
	{
		cin >> G->vexs[i];
	}

	// 读入Ne条边信息,建立邻接矩阵
	int i, j;
	WeightType w;
	for (int k = 0; k < G->Ne; k++)
	{
		cout << "输入边(Vi, Vj)的下标i、j及其权值w:";
		cin >> i >> j >> w;
		G->arcs[i][j] = w;
		G->arcs[j][i] = G->arcs[i][j];	// 无向图的邻接矩阵为对称阵
	}
}

/**************************************************************************************
********************************* 最小生成树之Prime算法 *********************************
***************************************************************************************/
void minSpanTreePrime(MGraph* G) {
	int adjvex[MAXVEX];
	WeightType lowcost[MAXVEX];	/* 保存相关顶点间边的权值
								   若lowcost[i]的值为0,表示下标为i的顶点已被纳入生成树中
								*/ 
								
	/* 初始化操作,从V0顶点开始构建最小生成树 */
	adjvex[0] = 0;		// 初始化第一个顶点的下标为0
	lowcost[0] = 0;		// 将lowcost[0]初始化为0,即将顶点V0纳入生成树
	for (int i = 1; i < G->Nv; i++)
	{
		lowcost[i] = G->arcs[0][i];	// 将V0与其邻接点之间的边上权值存入lowcost数组
		adjvex[i] = 0;				// 均初始化为V0的下标
	}

	for (int i = 1; i < G->Nv; i++)		// 这里循环从1开始,因为生成树有n-1条边
	{
		WeightType minVal = INFINITY;	// 记录最小权值,初始化为INFINITY
		int minIdx;						// 记录最小权值顶点下标
		for (int j = 0; j < G->Nv; j++)
		{
			if (lowcost[j] != 0 && lowcost[j] < minVal) {
				minVal = lowcost[j];
				minIdx = j;
			}
		}	// 找到权值最小的顶点下标

		cout << "(" << adjvex[minIdx] << ", " << minIdx << ")" << endl;	/* 打印当前顶点中权值最小的边
																		   也就是最小生成树中的一条边
																		*/ 
		lowcost[minIdx] = 0;	// 将当前顶点的权值置为0,表示它已被纳入生成树中

		// 将下标为minIdx的顶点加入生成树后,更新lowcost数组
		for (int k = 0; k < G->Nv; k++)
		{
			/*
			lowcost[k] != 0:表示不考虑已加入生成树的顶点
			G->arcs[minIdx][k]:表示顶点minIdx的邻接点Vk的权值
			G->arcs[minIdx][k] < lowcost[k]:若邻接点的权值小于当前lowcost[k]的值,则需要更新lowcost[k]
			*/
			if (lowcost[k] != 0 && G->arcs[minIdx][k] < lowcost[k]) {
				lowcost[k] = G->arcs[minIdx][k];
				adjvex[k] = minIdx;
			}
		}
	}
}

int main() {
	MGraph* G = new MGraph;
	createMGraph(G);

	minSpanTreePrime(G);

	delete G;
}

运行结果:
以《大话数据结构》图7-6-3为例。
在这里插入图片描述

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

算法思想:
设连通网N=(V,E),令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{}),每个顶点自成一个连通分量;
在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上(即:不能形成环),则将此边加入到T中,否则,舍去此边,选取下一条代价最小的边;
以此类推,直至T中所有顶点都在同一连通分量上为止。

Kruskal算法以边为目标,直接去找最小权值的边来构建最小生成树的,算法时间复杂度为O(eloge)

#include <iostream>
using namespace std;

/**************************************************************************************
*********************************** 图的边集数组表示 ***********************************
***************************************************************************************/
typedef int	 WeightType;	// 边上权值类型,自定义
typedef char VertexType;	// 顶点类型,自定义

#define MAXVEX	(100)	// 最大顶点数
#define MAXEDGE	(100)	// 最大边数

/* 边集数组的Edge结构定义 */
typedef struct {
	int begin;		// 存储边的起点下标
	int end;		// 存储边的终点下标
	WeightType w;	// 权值
} Edge;

typedef struct {
	VertexType vexs[MAXVEX];	// 顶点数组
	Edge edges[MAXEDGE];		// 边集数组
	int Nv, Ne;					// 顶点数,边数
} EGraph;

/**
* @brief:	创建图的边集数组表示
* @param G:指向图的指针
* @return:	void
*/
void createEGraph(EGraph* G) {
	cout << "输入顶点数和边数:";
	cin >> G->Nv >> G->Ne;

	cout << "输入顶点信息:";
	for (int i = 0; i < G->Nv; i++)
	{
		cin >> G->vexs[i];
	}

	// 读入Ne条边信息,建立边集数组
	int i, j;
	WeightType w;
	Edge e;
	for (int k = 0; k < G->Ne; k++)
	{
		cout << "输入边(Vi, Vj)的下标i、j及其权值w:";
		cin >> i >> j >> w;
		e.begin = i;
		e.end = j;
		e.w = w;
		G->edges[k] = e;
	}
}

/**
* @brief:	对边集合数组进行排序(采用冒泡排序)
* @param G:指向图的指针
* @return:	void
*/
void edgesSort(EGraph* G) {
	for (int i = 1; i < G->Ne; i++)
	{
		for (int j = 0; j < G->Ne - i; j++)
		{
			if (G->edges[j].w > G->edges[j+1].w)
			{
				Edge e = G->edges[j];
				G->edges[j] = G->edges[j + 1];
				G->edges[j + 1] = e;
			}
		}
	}

	/*
	// 打印排序后的结果
	for (int i = 0; i < G->Ne; i++)
	{
		cout << G->edges[i].w << "\t";
	}
	cout << endl;
	*/
}

/**************************************************************************************
******************************** 最小生成树之Kruskal算法 ********************************
***************************************************************************************/
int parent[MAXVEX] = { 0 };		// 辅助数组,用来判断边与边是否形成环路

/**
* @brief:		 查找连线顶点的尾部下标
* @param parent: 用来判断是否形成回路的数组
* @param f:		 顶点下标
* @return:		 int
*/
int Find(int* parent, int f) {
	while (parent[f] > 0)
	{
		f = parent[f];
	}
	return f;
}

/**
* @brief:	最小生成树Kruskal算法
* @param G: 指向图的指针
* @return:  void
*/
void minSpanTreeKruskal(EGraph* G) {
	int n, m;
	for (int i = 0; i < G->Ne; i++)	// 循环每一条边
	{
		n = Find(parent, G->edges[i].begin);
		m = Find(parent, G->edges[i].end);
		if (n != m)	// 假如n与m不等,说明此边没有与现有生成树形成环路
		{
			parent[n] = m;	/* 将此边的结尾顶点放入下标为起点的parent中,
							   表示此顶点已经在生成树集合中
							*/
			cout << "(" << G->edges[i].begin << ", " << G->edges[i].end << ")\t" 
				 << G->edges[i].w << endl;
		}
	}
}

int main() {
	EGraph* G = new EGraph;
	createEGraph(G);
	edgesSort(G);

	minSpanTreeKruskal(G);

	delete G;
}

运行结果:
以《大话数据结构》图7-6-7为例。
在这里插入图片描述

4. 两种算法比较

算法名PrimeKruskal
算法思想选择点选择边
时间复杂度O(n^2)(n为顶点数)O(eloge)(e为边数)
适应范围稠密图稀疏图

5. 参考书籍

大话数据结构-程杰
青岛大学数据结构-王卓
Kruskal算法
parent数组和Find函数的原理



这篇关于图的最小生成树--Prim算法与Kruskal算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程