最小生成树
最小生成树(minimum spanning tree)是由n个顶点,n-1条边,将一个连通图连接起来,且使权值最小的结构。
最小生成树可以用Prim(普里姆)算法或kruskal(克鲁斯卡尔)算法求出。
我们将以下面的带权连通图为例讲解这两种算法的实现:
注:由于测试输入数据较多,程序可以采用文件输入
Prim(普里姆)算法
时间复杂度:O(N^2)(N为顶点数)
prim算法又称“加点法”,用于边数较多的带权无向连通图
方法:每次找与之连线权值最小的顶点,将该点加入最小生成树集合中
注意:相同权值任选其中一个即可,但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树:
1.初始化:
lowcost[i]:表示以i为终点的边的最小权值,当lowcost[i]=0表示i点加入了MST。
mst[i]:表示对应lowcost[i]的起点,当mst[i]=0表示起点i加入MST。
由于我们规定最开始的顶点是1,所以lowcost[1]=0,MST[1]=0。即只需要对2~n进行初始化即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#define MAX 100
#define MAXCOST 0x7fffffff
int graph[MAX][MAX];
void prim( int graph[][MAX], int n)
{
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++)
{
lowcost[i] = graph[1][i]; //lowcost存放顶点1可达点的路径长度
mst[i] = 1; //初始化以1位起始点
}
mst[1] = 0;
|
2.查找最小权值及路径更新
定义一个最小权值min和一个最小顶点ID minid,通过循环查找出min和minid,另外由于规定了某一顶点如果被连入,则lowcost[i]=0,所以不需要担心重复点问题。所以找出的终点minid在MST[i]中可以找到对应起点,min为权值,直接输出即可。
我们连入了一个新的顶点,自然需要对这一点可达的路径及权值进行更新,所以循环中还应该包括路径更新的代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
for (i = 2; i <= n; i++)
{
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j]; //找出权值最短的路径长度
minid = j; //找出最小的ID
}
}
printf ( "V%d-V%d=%d " ,mst[minid],minid,min);
sum += min; //求和
lowcost[minid] = 0; //该处最短路径置为0
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < lowcost[j]) //对这一点直达的顶点进行路径更新
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
printf ( "最小权值之和=%d " ,sum);
}
|
具体代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#include<stdio.h>
#define MAX 100
#define MAXCOST 0x7fffffff
int graph[MAX][MAX];
void prim( int graph[][MAX], int n)
{
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++)
{
lowcost[i] = graph[1][i]; //lowcost存放顶点1可达点的路径长度
mst[i] = 1; //初始化以1位起始点
}
mst[1] = 0;
for (i = 2; i <= n; i++)
{
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j]; //找出权值最短的路径长度
minid = j; //找出最小的ID
}
}
printf ( "V%d-V%d=%d " ,mst[minid],minid,min);
sum += min; //求和
lowcost[minid] = 0; //该处最短路径置为0
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < lowcost[j]) //对这一点直达的顶点进行路径更新
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
printf ( "最小权值之和=%d " ,sum);
}
int main()
{
int i, j, k, m, n;
int x, y, cost;
//freopen("1.txt","r",stdin);//文件输入
scanf ( "%d%d" ,&m,&n); //m=顶点的个数,n=边的个数
for (i = 1; i <= m; i++) //初始化图
{
for (j = 1; j <= m; j++)
{
graph[i][j] = MAXCOST;
}
}
for (k = 1; k <= n; k++)
{
scanf ( "%d%d%d" ,&i,&j,&cost);
graph[i][j] = cost;
graph[j][i] = cost;
}
prim(graph, m);
return 0;
}
|
编译运行结果:
kruskal(克鲁斯卡尔)算法
时间复杂度:O(NlogN)(N为边数)
kruskal算法又称“加边法”,用于边数较少的稀疏图
方法:每次找图中权值最小的边,将边连接的两个顶点加入最小生成树集合中
注意:相同权值任选其中一个即可,但是不允许出现闭合回路的情况。
代码部分通过以下步骤可以得到最小生成树:
1.初始化:
构建边的结构体,包括起始顶点、终止顶点,边的权值
借用一个辅助数组vset[i]用来判断某边是否加入了最小生成树集合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#define MAXE 100
#define MAXV 100
typedef struct {
int vex1; //边的起始顶点
int vex2; //边的终止顶点
int weight; //边的权值
}Edge;
void kruskal(Edge E[], int n, int e)
{
int i,j,m1,m2,sn1,sn2,k,sum=0;
int vset[n+1];
for (i=1;i<=n;i++) //初始化辅助数组
vset[i]=i;
k=1; //表示当前构造最小生成树的第k条边,初值为1
j=0; //E中边的下标,初值为0
|
2.取边和辅助集合更新
按照排好的顺序依次取边,若不属于同一集合则将其加入最小生成树集合,每当加入新的边,所连接的两个点即纳入最小生成树集合,为避免重复添加,需要进行辅助集合更新
注:由于kruskal算法需要按照权值大小顺序取边,所以应该事先对图按权值升序,这里我采用了快速排序算法,具体算法可以参照快速排序(C语言)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
while (k<e) //生成的边数小于e时继续循环
{
m1=E[j].vex1;
m2=E[j].vex2; //取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点分属于不同的集合,该边是最小生成树的一条边
{ //防止出现闭合回路
printf ( "V%d-V%d=%d " ,m1,m2,E[j].weight);
sum+=E[j].weight;
k++; //生成边数增加
if (k>=n)
break ;
for (i=1;i<=n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
printf ( "最小权值之和=%d " ,sum);
}
|
具体算法实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#include <stdio.h>
#define MAXE 100
#define MAXV 100
typedef struct {
int vex1; //边的起始顶点
int vex2; //边的终止顶点
int weight; //边的权值
}Edge;
void kruskal(Edge E[], int n, int e)
{
int i,j,m1,m2,sn1,sn2,k,sum=0;
int vset[n+1];
for (i=1;i<=n;i++) //初始化辅助数组
vset[i]=i;
k=1; //表示当前构造最小生成树的第k条边,初值为1
j=0; //E中边的下标,初值为0
while (k<e) //生成的边数小于e时继续循环
{
m1=E[j].vex1;
m2=E[j].vex2; //取一条边的两个邻接点
sn1=vset[m1];
sn2=vset[m2];
//分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点分属于不同的集合,该边是最小生成树的一条边
{ //防止出现闭合回路
printf ( "V%d-V%d=%d " ,m1,m2,E[j].weight);
sum+=E[j].weight;
k++; //生成边数增加
if (k>=n)
break ;
for (i=1;i<=n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
printf ( "最小权值之和=%d " ,sum);
}
int fun(Edge arr[], int low, int high)
{
int key;
Edge lowx;
lowx=arr[low];
key=arr[low].weight;
while (low<high)
{
while (low<high && arr[high].weight>=key)
high--;
if (low<high)
arr[low++]=arr[high];
while (low<high && arr[low].weight<=key)
low++;
if (low<high)
arr[high--]=arr[low];
}
arr[low]=lowx;
return low;
}
void quick_sort(Edge arr[], int start, int end)
{
int pos;
if (start<end)
{
pos=fun(arr,start,end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
}
int main()
{
Edge E[MAXE];
int nume,numn;
//freopen("1.txt","r",stdin);//文件输入
printf ( "输入顶数和边数: " );
scanf ( "%d%d" ,&numn,&nume);
for ( int i=0;i<nume;i++)
scanf ( "%d%d%d" ,&E[i].vex1,&E[i].vex2,&E[i].weight);
quick_sort(E,0,nume-1);
kruskal(E,numn,nume);
}
|
编译运行结果:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:https://blog.csdn.net/qq_39630587/article/details/77427044