最小生成树

发表于 | 阅读数

最小生成树的两种算法 — Prim & Kruscal

什么是最小生成树

最小生成树是一副连通加权无向图中一棵权值最小的生成树。

在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 {\displaystyle (u,v)\in E}(u,v)\in E），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集且 (V, T) 为树，使得 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树 — Prim 算法

算法描述

  1. 准备：定义一个二维数组 dist 来存储每两个点之间的距离，定义一个一维数组 minc 来存储每个点到已经在最小生成树中的点的最小距离
  2. 初始化邻接矩阵，然后通过输入的数据来改变邻接矩阵
  3. 选择一个顶点 s 作为最小生成树中的点，初始化 minc 数组，其中 minc[s] 为 0 ，若其他点到 s 有边，则初始化为边的权重，否则初始化为 MAX 值
  4. 选择 minc 数组中不为 0 且最小的一个值对应的点，加入最小生成树，将该值变为 0，更新其他点到最小生成树中的点的最小距离
  5. 重复第三步操作直到所有的点都加入到最小生成树中

代码示例

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
#include <stdio.h>
#define M 5001
#define INF 99999999
int n,e1,e;
int dist[M][M];
int minc[M];

void solve(int s)
{
    int i,j,count=0,min,k;
    for(i=1;i<=n;i++)
    {
    	minc[i]=dist[s][i];
	}
    minc[s]=0;
    for(i=1;i<n;i++)
	{
        min=INF;
        for(j=1;j<=n;j++)
		{
            if(minc[j] && minc[j]<min)
			{
                min=minc[j];
                k=j;
            }
        }
        minc[k]=0;
        count+=min;
        for(j=1;j<=n;j++)
		{
            if(dist[k][j]<minc[j])
            {
            	minc[j]=dist[k][j];
			}
        }
    }
    printf("%d",count);
}

int main()
{
    int t1,t2,t3,i,j;
    for(i=0;i<M;i++)
    {
    	for(j=0;j<M;j++)
    	{
    		dist[i][j]=INF;
		}
	}
    scanf("%d%d",&n,&e);
    for(i=1;i<=e;i++)
	{
        scanf("%d%d%d",&t1,&t2,&t3);
        if(t3<dist[t1][t2])
        {
        	dist[t2][t1]=dist[t1][t2]=t3;
		}
    }
    solve(1);
    return 0;
}

最小生成树 — kruscal 算法

算法描述

  1. 准备：并查集的知识
  2. 用邻接链表存储每一条边，再用一个结构数组存储所有的边，将结构数组按照边的权值大小从小到大排序
  3. 遍历结构数组，如果一条边的两个端点的祖宗不同，则将起点的祖宗的祖宗设为终点的祖宗（有点绕嘴），否则直接跳到下一条边
  4. 重复 2 操作，直到所有的点都加入到了最小生成树中

代码示例

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
#include <stdio.h>
#include <stdlib.h>
int n,m,i,j,u,v,total;
struct edge{
	int start,to;
	long long val;
}bian[200005];
int f[100000];
long long ans;

int find(int x)
    if(f[x]==x)
    {
    	return x;
	}else 
    {
        f[x]=find(f[x]);
        return f[x];
    }   
}

void kruskal()
{

    for(i=1;i<=m;i++)
    {
        u=find(bian[i].start);
        v=find(bian[i].to);
        if(u==v) continue;
            ans+=bian[i].val;
            f[u]=v;
            total++;
            if(total==n-1) break;
    }
} 

int cmp(const void *ap,const void *bp)
{
	const struct edge *a=(struct edge *)ap;
	const struct edge *b=(struct edge *)bp;
	return a->val-b->val;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) 
    {
    	f[i]=i;
	}
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&bian[i].start,&bian[i].to,&bian[i].val);
    }
    qsort(bian+1,m,sizeof(struct edge),cmp);
    kruskal();
    printf("%d",ans);
    return 0;
}

注意事项

Prim 算法多用于稠密图，Kruscal 算法多用于稀疏图