欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的最小生成树:普利姆算法、克鲁斯卡尔算法

程序员文章站 2022-07-13 08:36:44
...
最小生成树(Minimum Cost Spanning Tree):对于一个带权值的图,即网结构,n个顶点,用n-1条边把一个连通图连接起来,并且使得权值的和最小。有两种算法:普利姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。
这两者都是基于邻接矩阵的。

普利姆(Prim)算法

普利姆算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。

思路:假设 N = (P, {E}) 是连通网, TE 是 N上最小生成树中边的集合。算法从 U = {u0}(u0 属于 V), TE = {} 开始。重复执行下述操作:在所有 u 属于 U, v属于 V-U 的边(u, v) 属于E 中找一条代价最小的边(u0, v0) 并加入集合 TE,同时 v0 并入 U ,直至 U = V 为止。此时TE中必有 n-1 条边,则 T = (V, {TE}) 为 N 的最小生成树。

此算法的时间复杂度为O[n2]
图的最小生成树:普利姆算法、克鲁斯卡尔算法

//Prim算法生成最小生成树
void MiniSpanTree_Prim(MGraph G)
{
	int min, i, j, k;
	int adjvex[MAXVEX];			//保存相关顶点下标
	int lowcost[MAXVEX];		//保存相关顶点间边的权值0
	lowcost[0] = 0;				//初始化第一个权值为0,即v0加入生成树。lowcost的值为0,,在这里就是此下标的顶点已经加入生成树
	adjvex[0] = 0;				//初始化第一个顶点下标为0
	for (i = 1; i < G.numVertexes; i++)
	{
		lowcost[i] = G.arc[0][i];
		adjvex[i] = 0;
	}
	for (i = 1; i < G.numVertexes; i++)
	{
		min = INFINITY;
		j = 1;
		k = 0;
		while (j < G.numVertexes)
		{
			if (lowcost[j] != 0 && lowcost[j] < min)
			{
				min = lowcost[j];
				k = j;
			}
			j++;
		}
	}
	printf("(%d, %d)", adjvex[k], k);
	lowcost[k] = 0;
	for (j = 1; j < G.numVertexes; j++)
	{
		if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
		{
			lowcost[j] = G.arc[k][j];
			adjvex[j] = k;
		}
	}
}

克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔算法是以边为目标构建,需要定义边集数组。

将邻接矩阵通过程序转化为边集数组,并将它们按权值从小到大排序。

此算法的Find() 函数由边数e决定,时间复杂度为O[log e],而外面有一个for循环,所有其算时间复杂度为O[elog e]。
图的最小生成树:普利姆算法、克鲁斯卡尔算法

//克鲁斯卡尔(Kruskal)算法
typedef struct
{
	int begin;
	int end;
	int weight;
}Edge;

//Kruskal算法生成最小生成树
void MiniSpanTree_Kruskal(MGraph G)
{
	int i, n, m;
	Edge edges[MAXEDGE];
	int parent[MAXVEX];
	//此处省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码
	for (i = 0; i < G.numVertexes; i++)
		parent[i] = 0;
	for (i = 0; i < G.numVertexes; i++)
	{
		n = Find(parent, edges[i].begin);
		m = Find(parent, edges[i].end);
		if (n != m)
		{
			parent[n] = m;
			printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
		}
	}
}

int Find(int* parent, int f)
{
	while (parent[f] > 0)
		f = parent[f];
	return f;
}

克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大优势。

而普利姆算法对于稠密图,即边数非常多的情况会更好一些。

相关标签: 数据结构