知识文档站

Appearance

最小生成树

基本介绍 ​

最小生成树：在无向带权图中选择择一些边，在 保证连通性的情况下，边的总权值最小 ​

最小生成树可能不只一棵，只要保证边的总权值最小，就都是正确的最小生成树 ​

如果无向带权图有 n 个点，那么最小生成树一定有 n-1 条边 ​

最小瓶颈树：在最小生成树的基础上，要求最大权值边的权值尽量小，直接求最小生成树即可 ​

扩展：最小生成树一定是最小瓶颈树（最后一题） ​

Kruskal 算法 ​

题目链接 ​

https://www.luogu.com.cn/problem/P3366 ​

思路模板 ​

（1）把所有的边，根据权值从小到大排序，从权值小的边开始考虑 ​

（2）如果连接当前的边不会形成环，就选择当前的边 ​

（3）如果连接当前的边会形成环，就不要当前的边 ​

（4）考察完所有边之后，最小生成树的也就得到了 ​

时间复杂度 O（m * log m） + O（n） + O（m），m 为边的数量 ​

代码实现 ​

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

public class Main {

    public static int MAXN = 5001;

    public static int MAXM = 200001;

    public static int[] father = new int[MAXN];

    // u -> v，权值为 w
    public static int[][] edges = new int[MAXM][3];

    public static int n, m;

    public static void build() {
        for (int i = 1; i <= n; i++) {
            // 初始指向自己
            father[i] = i;
        }
    }

    public static int find(int n) {
        if (n == father[n]) {
            return n;
        }
        return father[n] = find(father[n]);
    }

    // 判断是否在一个集合中，在就返回 false，否则返回 true
    public static boolean union(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx == fy) {
            return false;
        } else {
            father[fx] = fy;
            return true;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            in.nextToken();
            m = (int) in.nval;
            build();
            for (int i = 0; i < m; i++) {
                in.nextToken();
                edges[i][0] = (int) in.nval;
                in.nextToken();
                edges[i][1] = (int) in.nval;
                in.nextToken();
                edges[i][2] = (int) in.nval;
            }
            // 边按照权值从小到大排序
            Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);
            int ans = 0;
            // 最小生成树一定有 n-1 条边
            int edgeCnt = 0;
            for (int[] edge : edges) {
                // 如果不在一个集合中，则合并
                if (union(edge[0], edge[1])) {
                    edgeCnt++;
                    // 统计权值
                    ans += edge[2];
                }
            }
            out.println(edgeCnt == n - 1 ? ans : "orz");
        }
        out.flush();
        out.close();
        br.close();
    }
}

Prim 算法（不常用） ​

题目链接 ​

https://www.luogu.com.cn/problem/P3366 ​

思路分析 ​

解锁的点的集合叫 set（普通集合）、解锁的边的集合叫 heap（小根堆）。set 和 heap都为空 ​

可从任意点开始，开始点加入到 set，开始点的所有边加入到 heap ​

从 heap 中弹出权值最小的边 e，查看边 e 所去往的点 x ​

A. 如果 x 已经在 set 中，边 e 舍弃，重复步骤3 ​

B. 如果 x 不在 set 中，边e属于最小生成树，把 x 加入 set，重复步骤3 ​

当 heap 为空，最小生成树的也就得到了 ​

时间复杂度 O（n + m） + （m * log m），m 为边的数量 ​

代码实现 ​

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            List<List<int[]>> graph = new ArrayList<>();
            int n = (int) in.nval;
            for (int i = 0; i <= n; i++) {
                graph.add(new ArrayList<>());
            }
            in.nextToken();
            int m = (int) in.nval;
            for (int i = 0, u, v, w; i < m; i++) {
                in.nextToken();
                u = (int) in.nval;
                in.nextToken();
                v = (int) in.nval;
                in.nextToken();
                w = (int) in.nval;
                graph.get(u).add(new int[] { v, w });
                graph.get(v).add(new int[] { u, w });
            }
            // int[0]：到达的节点，int[1]：到达的花费
            PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
            // 默认从 1 号点出发
            for (int[] edge : graph.get(1)) {
                heap.add(edge);
            }
            // 记录访问过的节点
            boolean[] set = new boolean[n + 1];
            int nodeCnt = 1;
            set[1] = true;
            int ans = 0;
            while (!heap.isEmpty()) {
                int[] edge = heap.poll();
                int next = edge[0];
                int cost = edge[1];
                if (!set[next]) {
                    nodeCnt++;
                    set[next] = true;
                    ans += cost;
                    for (int[] e : graph.get(next)) {
                        heap.add(e);
                    }
                }
            }
            out.println(nodeCnt == n ? ans : "orz");
        }
        out.flush();
        out.close();
        br.close();
    }
}

水资源分配优化 ​

题目描述 ​

村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水 ​

对于每个房子 i，我们有两种可选的供水方案 ​

一种是直接在房子内建造水井，成本为 wells [ i - 1 ] （注意 -1，因为 索引从 0 开始） ​

另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes [ j ] = [ house1 j，house2 j，cost j ]，代表用管道将 house1 j 和 house2 j 连接在一起的成本。连接是双向的 ​

请返回为所有房子都供水的最低总成本 ​

n：2 ≤ n ≤ 10⁴ ​

wells.length：等于 n ​

wells [ i ]：0 ≤ wells [ i ] ≤ 10⁵ ​

pipes.length：1 ≤ pipes.length ≤ 10⁴ ​

pipes [ j ] .length：等于 3 ​

house1ⱼ, house2ⱼ：1 ≤ house1ⱼ, house2ⱼ ≤ n 且 house1ⱼ ≠ house2ⱼ ​

costⱼ：0 ≤ costⱼ ≤ 10⁵ ​

思路分析 ​

假设有一个水源点，依次连通所有村庄，就相当于单独打井，还有就是村庄之间连通求最小生成树，比较一下两个权值即可 ​

代码实现 ​

java
class Solution {
	public static int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
		build(n);
        // 假设有一水源点，分别连通村庄，相当于单独打井
		for (int i = 0; i < n; i++, cnt++) {
			// wells : 100   30
			//         0(1)  1(2)
			edges[cnt][0] = 0;
			edges[cnt][1] = i + 1;
			edges[cnt][2] = wells[i];
		}
        // 村庄之间连通
		for (int i = 0; i < pipes.length; i++, cnt++) {
			edges[cnt][0] = pipes[i][0];
			edges[cnt][1] = pipes[i][1];
			edges[cnt][2] = pipes[i][2];
		}
        // kruskal 算法，根据边的权值从小到大排序
		Arrays.sort(edges, 0, cnt, (a, b) -> a[2] - b[2]);
		int ans = 0;
		for (int i = 0; i < cnt; i++) {
			if (union(edges[i][0], edges[i][1])) {
				ans += edges[i][2];
			}
		}
		return ans;
	}

	public static int MAXN = 10010;

    // 分两种情况，所以边数量为 2 倍
	public static int[][] edges = new int[MAXN << 1][3];

	public static int cnt;

	public static int[] father = new int[MAXN];

	public static void build(int n) {
		cnt = 0;
		for (int i = 0; i <= n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	// 如果x和y，原本是一个集合，返回false
	// 如果x和y，不是一个集合，合并之后后返回true
	public static boolean union(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) {
			father[fx] = fy;
			return true;
		} else {
			return false;
		}
	}
}

检查边长度限制的路径是否存在 ​

题目链接 ​

https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths/ ​

思路分析 ​

本题考查并查集的应用，并结合最小生成树 ​

将所有问题按照边的权值从小到大排序，遍历每一个问题，以当前问题的权值要求为基准，遍历所有边，符合要求的就合并，最后看一下每个问题中的两个点是否在同一个集合中即可 ​

代码实现 ​

java
class Solution {
    public static boolean[] distanceLimitedPathsExist(int n, int[][] edges, int[][] queries) {
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        int m = edges.length;
        int k = queries.length;
        for (int i = 0; i < k; i++) {
            questions[i][0] = queries[i][0];
            questions[i][1] = queries[i][1];
            questions[i][2] = queries[i][2];
            // 每个问题对应一个答案数组中的下标
            questions[i][3] = i;
        }
        Arrays.sort(questions, 0, k, (a, b) -> a[2] - b[2]);
        build(n);
        // 问题的长度为 k
        boolean[] ans = new boolean[k];
        for (int i = 0, j = 0; i < k; i++) {
            // i : 问题编号
            // j : 边的编号
            for (; j < m && edges[j][2] < questions[i][2]; j++) {
                union(edges[j][0], edges[j][1]);
            }
            // 如果不在一个集合中，则说明两点之间路径中的权重存在大于 limit 的边
            ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);
        }
        return ans;
    }

    public static int MAXN = 100001;

    // u -> v，权值为 w，z 记录答案数组中对应的下标
    public static int[][] questions = new int[MAXN][4];

    public static int[] father = new int[MAXN];

    public static void build(int n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
    }

    public static int find(int i) {
        if (i != father[i]) {
            father[i] = find(father[i]);
        }
        return father[i];
    }

    public static boolean isSameSet(int x, int y) {
        return find(x) == find(y);
    }

    public static void union(int x, int y) {
        father[find(x)] = find(y);
    }
}

繁忙的都市（最小瓶颈树） ​

题目链接 ​

https://www.luogu.com.cn/problem/P2330 ​

思路分析 ​

结论：最小生成树一定是最小瓶颈树，证明略，直接跑 kruskal 算法求解即可 ​

代码实现 ​

java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {

	public static int MAXN = 301;

	public static int MAXM = 8001;

	public static int[] father = new int[MAXN];

	public static int[][] edges = new int[MAXM][3];

	public static int n, m;

	public static void build() {
		for (int i = 1; i <= n; i++) {
			father[i] = i;
		}
	}

	public static int find(int i) {
		if (i != father[i]) {
			father[i] = find(father[i]);
		}
		return father[i];
	}

	// 如果 x 和 y 本来就是一个集合，返回false
	// 如果 x 和 y 不是一个集合，合并之后返回true
	public static boolean union(int x, int y) {
		int fx = find(x);
		int fy = find(y);
		if (fx != fy) {
			father[fx] = fy;
			return true;
		} else {
			return false;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			build();
			for (int i = 0; i < m; i++) {
				in.nextToken();
				edges[i][0] = (int) in.nval;
				in.nextToken();
				edges[i][1] = (int) in.nval;
				in.nextToken();
				edges[i][2] = (int) in.nval;
			}
            // Kruskal，将边按照权值从小到大排序
			Arrays.sort(edges, 0, m, (a, b) -> a[2] - b[2]);
			int ans = 0;
			int edgeCnt = 0;
			for (int[] edge : edges) {
				if (union(edge[0], edge[1])) {
					edgeCnt++;
					ans = Math.max(ans, edge[2]);
				}
			}
			out.println((n - 1) + " " + ans);
		}
		out.flush();
		out.close();
		br.close();
	}
}

Copyright © 2025 Jackson 凌 All Rights Reserved. | 粤ICP备2025441629号-1