再次温习最小生成树的一些思路

算法重温
字数统计: 2.3k字   |   阅读时长: 12分

写在前面

因为之前4月份打了将近一个月的个人赛，有些以前学习过的算法已经忘了，所以重新再温习一遍。

关于最小生成树

最小生成树（minimum spanning tree）是由n个顶点，n-1条边，将一个连通图连接起来，且使权值最小的结构。
最小生成树可以用Prim（普里姆）算法或kruskal（克鲁斯卡尔）算法求出。

Kruskal算法详解及模板与例题

Kruskal算法简介

Kruskal算法是基于并查集算法而进行的，很简单的思路就是，对一张图，将所有的边都拆出来，然后对每条边的边权进行排序（从大到小，从小到大看题目需要），然后再将边连回去，连边的时候判断两个点是否被连通了，如果是连通的，那么就将该边扔了再看下一条边，如果没有被连通，那么就将该条边连上，然后用并查集合并即可。

时间复杂度：O（NlogN）（N为边数）
kruskal算法又称“加边法”，用于边数较少的稀疏图
方法：每次找图中权值最小的边，将边连接的两个顶点加入最小生成树集合中
注意：相同权值任选其中一个即可，但是不允许出现闭合回路的情况。

Kruskal算法图解

tupian1

tupian2

tupian3

tupian4

tupian5

tupian6

Kruskal算法代码详解及模板

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
#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 200010;
const int inf = 0x3f3f3f3f;
using namespace std;
int pre[maxx];
int n;
struct node//存边权值
{
    int s;
    int e;
    int v;
} edge[maxx];
bool cmp(node a, node b)//看情况修改 优先级给小边权还是大边权
{
    return a.v < b.v;
}
void init()//初始化
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}
int getf(int a)//并查集 看两点是否在同一个图内
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    return pre[a] = tmp;
}
int Kruskal(int a, int b) //并查集合并操作，看是否在同一个图内 如果在就跳过 不在就合并
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
    {
        pre[fa] = fb;
        return 1;
    }
    else
        return 0;
}
int main()
{
    while (~scanf("%d", &n), n)
    {
        init();
        int m = (n * (n - 1)) / 2;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &edge[i].s, &edge[i].e, &edge[i].v);
        sort(edge + 1, edge + m + 1, cmp);
        int ans = 0;
        for (int i = 1; i <= m; i++)
        {
            if (Kruskal(edge[i].s, edge[i].e))
                ans += edge[i].v;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Kruskal算法例题

例题一：POJ-1287

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
#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
typedef long long ll;
const int maxx = 10010;
const int mod = 10007;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
using namespace std;
struct node
{
    int s;
    int e;
    int v;
} edge[maxx];
bool cmp(node a, node b)
{
    return a.v < b.v;
}
int pre[maxx];
int n, r;
void init()
{
    for (int i = 0; i <= n; i++)
        pre[i] = i;
}
int getf(int a)
{
    if (pre[a] == a)
        return a;
    int tmp = getf(pre[a]);
    return pre[a] = tmp;
}
int Kruskal(int a, int b)
{
    int fa = getf(a);
    int fb = getf(b);
    if (fa != fb)
    {
        pre[fa] = fb;
        return 1;
    }
    else
        return 0;
}
int main()
{
    while (~scanf("%d%d", &n, &r), n)
    {
        init();
        for (int i = 1; i <= r; i++)
            scanf("%d%d%d", &edge[i].s, &edge[i].e, &edge[i].v);
        sort(edge + 1, edge + r + 1, cmp);
        int ans = 0;
        for (int i = 1; i <= r; i++)
        {
            if (Kruskal(edge[i].s, edge[i].e))
                ans += edge[i].v;
        }
        printf("%d\n", ans);
    }
    return 0;
}

Prim算法详解及模板与例题

Prim算法简介

时间复杂度：O（N^2）（N为顶点数）
prim算法又称“加点法”，用于边数较多的带权无向连通图
方法：每次找与之连线权值最小的顶点，将该点加入最小生成树集合中
注意：相同权值任选其中一个即可，但是不允许出现闭合回路的情况。

Prim算法图解

tupian1

tupian2

tupian3

tupian4

tupian5

tupian6

tupian7

Prim算法代码详解及模板

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
#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
typedef long long ll;
const int maxx = 210;
const int mod = 10007;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
using namespace std;
int mapp[maxx][maxx]; //存图
int dis[maxx];        //记录任意一点到这个点的最近距离
bool vis[maxx];       //用来标记0和1  表示这个点是否被选择过
int n;
void Prim()
{
    int sum = 0;
    int now;
    for (int i = 1; i <= n; i++) //初始化
    {
        dis[i] = inf;
        vis[i] = false;
    }
    for (int i = 1; i <= n; i++) //选择1为起始点，初始化
        dis[i] = mapp[1][i];
    dis[1] = 0;                 //起点的上一个节点没有节点，所以为0
    vis[1] = true;              //定义起点已经加入了最小生成树
    for (int i = 1; i < n; i++) //循环找最小边，循环n-1次
    {
        now = inf;
        int minn = inf;
        for (int j = 1; j <= n; j++) //找dis最小的节点并加入最小生成树
        {
            if (!vis[j] && dis[j] < minn)
            {
                now = j;//找出最小的顶点
                minn = dis[j];//找出权值最短的路径长度
            }
        }
        if (now == inf)
            break; //防止不成图
        vis[now] = true;
        sum += minn;//求和
        for (int j = 1; j <= n; j++) //添入新点后更新最小距离
        {
            if (!vis[j] && dis[j] > mapp[now][j])
                dis[j] = mapp[now][j];
        }
    }
    printf("%d\n", sum);
}
int main()
{
    while (~scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i++) //初始化邻接矩阵
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                    mapp[i][j] = 0;
                else
                    mapp[i][j] = inf;
            }
        int a,b,c;
        for (int i = 1; i < n; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            mapp[a][b] = mapp[b][a] = c;
        }
        Prim();
    }
    return 0;
}

Prim算法例题

例题一：POJ-1251

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
82
83
84
85
86
87
88
#include <stdio.h>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
typedef long long ll;
const int maxx = 210;
const int mod = 10007;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
using namespace std;
int mapp[maxx][maxx];
int dis[maxx];
bool vis[maxx];
int n;
void Prim()
{
    int sum = 0;
    int now;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = inf;
        vis[i] = false;
    }
    for (int i = 1; i <= n; i++)
        dis[i] = mapp[1][i];
    dis[1] = 0;
    vis[1] = true;
    for (int i = 1; i < n; i++)
    {
        now = inf;
        int minn = inf;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] < minn)
            {
                now = j;
                minn = dis[j];
            }
        }
        if (now == inf)
            break;
        vis[now] = true;
        sum += minn;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] > mapp[now][j])
                dis[j] = mapp[now][j];
        }
    }
    printf("%d\n", sum);
}
int main()
{
    char a, b;
    int num1, num2;
    int x, y;
    while (~scanf("%d", &n), n)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                    mapp[i][j] = 0;
                else
                    mapp[i][j] = inf;
            }

        for (int i = 1; i < n; i++)
        {
            cin >> a >> num1;
            for (int j = 1; j <= num1; j++)
            {
                cin >> b >> num2;
                x = a - 64;
                y = b - 64;
                mapp[x][y] = mapp[y][x] = num2;
            }
        }
        Prim();
    }
    return 0;
}

例题二：Hihocoder-1097

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>
#include <string>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
typedef long long ll;
const int maxx = 10010;
const int mod = 10007;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
using namespace std;
int mapp[maxx][maxx];
int dis[maxx];
bool vis[maxx];
int n;
void Prim()
{
    int sum = 0;
    int now;
    for (int i = 1; i <= n; i++)
    {
        dis[i] = inf;
        vis[i] = false;
    }
    for (int i = 1; i <= n; i++)
        dis[i] = mapp[1][i];
    dis[1] = 0;
    vis[1] = true;
    for (int i = 1; i < n; i++)
    {
        now = inf;
        int minn = inf;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] < minn)
            {
                now = j;
                minn = dis[j];
            }
        }
        if (now == inf)
            break;
        vis[now] = true;
        sum += minn;
        for (int j = 1; j <= n; j++)
        {
            if (!vis[j] && dis[j] > mapp[now][j])
                dis[j] = mapp[now][j];
        }
    }
    printf("%d\n", sum);
}
int main()
{
    while (~scanf("%d", &n))
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i == j)
                    mapp[i][j] = 0;
                else
                    mapp[i][j] = inf;
            }
        int a;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                scanf("%d", &a);
                if (a < mapp[i][j])
                    mapp[i][j] = mapp[j][i] = a;
            }
        Prim();
    }
    return 0;
}

赏

×

纯属好玩

扫码支持
扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦

本文标题:再次温习最小生成树的一些思路

文章作者:Stephencurry6666

发布时间:2020年05月12日 - 16时30分

最后更新:2020年05月12日 - 17时20分

原始链接:https://stephencurry6666.github.io/2020/05/12/%E5%86%8D%E6%AC%A1%E6%B8%A9%E4%B9%A0%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E7%9A%84%E4%B8%80%E4%BA%9B%E6%80%9D%E8%B7%AF/

许可协议: "署名-非商用-相同方式共享 3.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 写在前面
  2. 2. 关于最小生成树
  3. 3. Kruskal算法详解及模板与例题
    1. 3.1. Kruskal算法简介
    2. 3.2. Kruskal算法图解
    3. 3.3. Kruskal算法代码详解及模板
    4. 3.4. Kruskal算法例题
  4. 4. Prim算法详解及模板与例题
    1. 4.1. Prim算法简介
    2. 4.2. Prim算法图解
    3. 4.3. Prim算法代码详解及模板
    4. 4.4. Prim算法例题
,
字数统计：87.6k 载入天数...载入时分秒...