Prim算法--最小生成树

发表于 2022-07-21 分类于 acwing算法基础课笔记 Artalk： loading...

最小生成树 Prim 贪心稠密图

Prim算法，用来求解「加权连通图」的最小生成树，适用「稠密图」

最小生成树：
即连通图的「最小权重」生成树

Prim属于贪心算法，维持一个顶点集合

基于边集的Kruskal算法同样属于贪心算法，适用于「稀疏图」

朴素Prim算法

$n$ 代表顶点数量， $m$ 代表边的数量

时间复杂度为 $\Omicron(n^2)$

算法流程

图中所有顶点集合设为 $V$ ，维持一个顶点集合 $V_{new}=S$ 表示已经加入生成树的顶点

记 $V^{'}=V - V_{new}$ 为点集 $S$ 的补集

1.初始化距离数组 $dist[] = \text{INF}$ ，表示每个顶点到生成树（即集合 $S$ ）的最短距离

2.选取一个顶点加入 $S$

3.迭代 $n$ - $1$ 次

每次迭代，找到补集 $V^{'}$ 中，到集合 $S$ 距离最短的点： $t$
将顶点 $t$ 加入集合 $S$
用新加入的点 $t$ 去更新 $dist[]$

在每次迭代中，如果当前 $V^{'}$ 距离 $S$ 最短为 $\text{INF}$ 的话，意味着：

当前图不存在最小生成树，或者说当前图有多个连通分量，或者说存在「生成森林」

可直接返回

Tips

1.

Prim算法和Dijkstra算法的区别在于

$\text{Prim}$ 算法中的 $dist[]$ 数组表示的是，每个顶点到生成树（即集合 $S$ ）的最短距离

$\text{Dijkstra}$ 中的 $dist[]$ 表示的是，每个顶点到源点的最短距离

2.

最小生成树，可以用于求解：不同城市之间铺设铁路，求总铁路长度最短的方案等问题

3.

注意，最小生成树，根本上还是一颗树，满足树的全部性质

树是图的子集，是有向无环图

代码实现

核心代码

解析见注释

int prim() {
    // 初始化dist[]数组
    Arrays.fill(dist, INF);
    // 先选取一个点加入S，这里是选择1号点
    st[1] = true;
    for (int j = 1; j <= n; ++j) {
        dist[j] = Math.min(dist[j], g[1][j]);
    }

    int res = 0;
    for (int i = 1; i < n; ++i) {
        // 找到S集合外的，距离S最小的点
        int t = -1;
        for (int j = 1; j <= n; ++j) {
            if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        // 如果S集合外距离最短为INF，即不存在最小生成树，当前图非连通
        if (dist[t] == INF) return INF;

        res += dist[t]; // 积累总权重
        st[t] = true; // 加入到生成树中

        // 用新加入的顶点t来更新dist[]
        for (int j = 1; j <= n; ++j) {
            dist[j] = Math.min(dist[j], g[t][j]);
        }
    }
    return res;
}

java版完整代码

acwing 858. Prim算法求最小生成树

给定一个 $n$ 个点 $m$ 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible

import java.util.*;
import java.io.*;

class Main {
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 510;
    static final int INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m;

    static int prim() {
        // 初始化dist[]数组
        Arrays.fill(dist, INF);
        // 先选取一个点加入S，这里是选择1号点
        st[1] = true;
        for (int j = 1; j <= n; ++j) {
            dist[j] = Math.min(dist[j], g[1][j]);
        }

        int res = 0;
        for (int i = 1; i < n; ++i) {
            // 找到S集合外的，距离S最小的点
            int t = -1;
            for (int j = 1; j <= n; ++j) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
            }
            // 如果S集合外距离最短为INF，即不存在最小生成树，当前图非连通
            if (dist[t] == INF) return INF;

            res += dist[t]; // 积累总权重
            st[t] = true; // 加入到生成树中

            // 用新加入的顶点t来更新dist[]
            for (int j = 1; j <= n; ++j) {
                dist[j] = Math.min(dist[j], g[t][j]);
            }
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        int a, b, w;
        for (int i = 1; i <= n; ++i) {
            Arrays.fill(g[i], INF);
        }
        while (m-- > 0) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]);
            b = Integer.parseInt(str[1]);
            w = Integer.parseInt(str[2]);
            g[a][b] = Math.min(g[a][b], w); // 注意是无向图
            g[b][a] = g[a][b];
        }

        // begin here
        int t = prim();
        if (t == INF) log.write("impossible\n");
        else log.write(String.valueOf(t));

        //
        log.flush();
        log.close();
        cin.close();
    }
}

堆优化

算法整体和 $Dijkstra$ 很相似，同样可以进行堆优化

原理不再分析

堆优化版本的时间复杂度为 $\Omicron(m\log n)$ 的，适用于稀疏图，但是稀疏图的话，写 $\text{Kruskal}$ 更方便，因此堆优化版本的 $\text{Prim}$ 算法不常用

核心代码👇🏻

int prim() {
    // 初始化dist[]数组
    Arrays.fill(dist, INF);

    int res = 0;
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> {
        return a[1] - b[1];
    });
    // 先选取一个点加入S作为树根，这里是选择1号点
    heap.offer(new int[]{1, INF});
    int cnt = 0; // 记录生成树中节点的数量
    while (!heap.isEmpty()) {
        int[] cur = heap.poll();
        int ver = cur[0], distance = cur[1];
        if (st[ver]) continue;
        if (ver != 1) res += distance;
        cnt++;
        st[ver] = true;
        for (int i = 1; i <= n; ++i) {
            if (g[ver][i] == INF || i == ver) continue;
            if (dist[i] > g[ver][i]) {
                dist[i] = g[ver][i];
                heap.offer(new int[]{i, dist[i]});
            }
        }
    }
    // 如果生成树中节点数量少于n,说明图不连通，不存在最小生成树
    return cnt == n ? res : INF;
}

java版完整代码

import java.util.*;
import java.io.*;

class Main {
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 510;
    static final int INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m;
    
    static int prim() {
        // 初始化dist[]数组
        Arrays.fill(dist, INF);
       
        int res = 0;
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)->{return a[1] - b[1];});
         // 先选取一个点加入S作为树根，这里是选择1号点
        heap.offer(new int[]{1, INF});
        int cnt = 0; // 记录生成树中节点的数量
        while (!heap.isEmpty()) {
            int[] cur = heap.poll();
            int ver = cur[0], distance = cur[1];
            if (st[ver]) continue;
            if (ver != 1) res += distance;
            cnt++;
            st[ver] = true;
            for (int i = 1; i <= n; ++i) {
                // 如果存在自环，需要排除
                if (g[ver][i] == INF || i == ver) continue;
                if (dist[i] > g[ver][i]) {
                    dist[i] = g[ver][i];
                    heap.offer(new int[]{i, dist[i]});
                }
            }
        }
        // 如果生成树中节点数量少于n,说明图不连通，不存在最小生成树
        return cnt == n ? res : INF;
    }

    public static void main(String[] args) throws Exception {
        String[] str = cin.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        int a, b, w;
        for (int i = 1; i <= n; ++i) {
            Arrays.fill(g[i], INF);
        }
        while (m-- > 0) {
            str = cin.readLine().split(" ");
            a = Integer.parseInt(str[0]);
            b = Integer.parseInt(str[1]);
            w = Integer.parseInt(str[2]);
            g[a][b] = Math.min(g[a][b], w); // 考虑有重边
            g[b][a] = g[a][b]; // 无向图
        }

        // begin here
        int t = prim();
        if (t == INF) log.write("impossible\n");
        else log.write(String.valueOf(t));

        //
        log.flush();
        log.close();
        cin.close();
    }
}

📔博文图谱

提及本博文的链接

Kruskal算法–最小生成树