最小生成树

定义

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
——百度百科

Kruskal

思路

用贪心的思想，把所有的边从短到长排序，从最短的边开始判断，如果连接的两个点不是已经联通的，那就把这条边连起来。如果已经联通，则忽略这条边。

用并查集维护所有的点，联通的点在同一集合，从而判断点是否联通。

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define MAXN 110

int n, m, f[MAXN];

struct EDGE
{
    int u, v, w;
} E[MAXN * MAXN];

bool cmp(EDGE x, EDGE y)    //边从小到大排序
{
    return x.w < y.w;
}

void Init(int x)    //并查集初始化
{
    for (int i = 1; i <= x; i++) f[i] = i;
}

int Find(int x)
{
    return x == f[x] ? x : f[x] = Find(f[x]);
}

void Kruskal(int n, int m)
{
    int res = 0;    // 存放结果
    int num = 0;    // 记录当前选择了多少条边
    Init(m);
    sort(E + 1, E + 1 + m, cmp);
    for (int i = 1; i <= m; i++)
    {
        int f1 = Find(E[i].u);    //  查询u顶点在哪个集合中
        int f2 = Find(E[i].v);    //  查询v顶点在哪个集合中
        if (f1 != f2)    //  如果不在同一个集合中
        {
            num++;    //  选中的边数 +1
            res += E[i].w;    //  答案加上这条边的权值
            f[f1] = f2;    //  将这两个点合并到一个集合中
        }
        if (num == n - 1)    // 如果已经找到了 n - 1条边，说明最小生成树已经构建完成了
            break;
    }
    if (num == n - 1) printf("%d\n", res);
    else  puts("Impossible\n");
}

int main() 
{
    //freopen("in.txt", "r", stdin);

    while (scanf("%d %d", &n, &m) != EOF)    //n 个点，m 条边
    {
        if (!m) break;
        for (int i = 1; i <= m; i++)
            scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
        Kruskal(n, m);
    }
    
    return 0;
    
}

复杂度 · $O(m \ log m)$

Prim

思路

选用图中的任意一个顶点 $V_{0}$ ，从 $v_{0}$ 开始生成最小生成树
初始化 $d[v_{0}] \ = \ 0$ ，其他的点的距离值 $d[i] \ = \ INF$ ，其中 $d[i]$ 表示当前这棵小树到其他点的最小距离值
经过 N 次如下步骤操作，最后得到一个含 N 各顶点，N - 1 条边的最小生成树
1. 选择一个未标记的点 K，并且 $d[K]$ 的值是最小的
2. 标记点 K 进入这棵小树
3. 以 K 为中间点，更新这棵小树到未标记点的距离的最小值
得到最小生成树 T

模板

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 110

int n, m, mp[MAXN][MAXN], vis[MAXN], d[MAXN];

void Initmap(int x)
{
    memset(mp, INF, sizeof(mp));
    for (int i = 1; i <= x; i++) mp[i][i] = 0;
}

void Prim(int n, int m)
{
    memset(vis, 0, sizeof(vis));
    int index = 1;    //当前加入到小树的顶点
    int res = 0;    //存放结果
    vis[index] = 1;
    for (int i = 1; i <= n; i++)    //更新这个点到其他点的距离  
        d[i] = mp[index][i];
    for (int i = 1; i < n; i++)    //执行 n - 1 次，找剩下的n - 1 个点
    {
        int minn = INF;
        for (int j = 1; j <= n; j++)    //找出未加入小树且 d 最小的点
        {
            if (!vis[j] && d[j] < minn)
            {
                minn = d[j];
                index = j;
            }
        }
        if (minn == INF)    //如果没有找到，说明不存在最小生成树
        {
            printf("Impossible\n");
            return;
        }
        res += minn;    //累加答案
        vis[index] = 1;    //将这个点加入最小生成树中
        for (int j = 1; j <= n; j++)    //更新这个点加入后，当前这棵小树到未加入的点的最近距离
        {
            if (!vis[j] && d[j] > mp[index][j]) d[j] = mp[index][j];
        }
    }
    printf("%d\n", res);
}
int main()
{
    //freopen("in.txt", "r", stdin);

    while (scanf("%d%d", &n, &m) != EOF)
    {
        if (!m) break;
        Initmap(n);
        for (int i = 1, u, v, w; i <= m; i++)
        {
            scanf("%d%d%d", &u, &v, &w);
            mp[v][u] = min(w, mp[u][v]);
            mp[u][v] = min(w, mp[u][v]);    // 消除重边的影响
        }
        Prim(n, m);
    }
    
    return 0;
    
}

最小生成树

最小生成树

最小生成树

定义

Kruskal

思路

模板

复杂度 · O(m logm)O(m \ log m)O(m logm)

Prim

思路

模板

复杂度 · O(n2)O(n^{2})O(n2)

复杂度 · $O(m \ log m)$

复杂度 · $O(n^{2})$