图的最小生成树:普利姆算法、克鲁斯卡尔算法
程序员文章站
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;
}
克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大优势。
而普利姆算法对于稠密图,即边数非常多的情况会更好一些。
下一篇: 用数组来存储信息