mobile wallpaper 1
mobile wallpaper 2
mobile wallpaper 3
mobile wallpaper 4
Profile Image of the Author
Stella
近期公告
博客搬迁中wordpress --> astro
标签
4738 字
13 分钟
最短路算法和最小生成树
2026-03-12
算法
算法
/
图论
/
最短路
/
最小生成树

最短路算法合集#

常见的最短路问题

单源最短路：求一个点到其他所有点的最短距离（n 为点数，m 为边数）

  • 所有边权都是正数时：
    • 朴素 Dijkstra 算法 O(n²)——适用于稠密图（m 接近 n²），邻接矩阵存图；
    • 堆优化版的 Dijkstra 算法 O(m log n)——适用于稀疏图，邻接表 + 小根堆；
  • 存在负权边时：
    • ==在存在负权边的时候最短路是不一定存在的，如果能求出最短路径，那么这个图中就不能存在负权回路==——负环上每绕一圈总距离都会变小，可以无限绕下去，最短路就失去了定义；
    • Bellman-Ford 算法 O(nm)——能处理负权边，还能求”最多经过 k 条边”的最短路；
    • SPFA（Bellman-Ford 的队列优化版）平均 O(m)，最坏 O(nm)——实际运行通常很快，但可能被特殊数据卡到最坏。

为什么有负权边时 Dijkstra 会失效？ Dijkstra 的贪心前提是”一个点一旦被确定，它的最短距离之后不会再变小”。边权全为正时，绕路只会更远，这个前提成立；而负权边可能让某个”已经确定”的点通过一条负边变得更小，贪心结论被推翻，所以 Dijkstra 不能处理负权边。

多源汇最短路： 起点和终点都不确定的最短路问题

Floyd 算法 O(n ^ 3)——一次预处理求出任意两点之间的最短距离，适合 n 较小（如 n ≤ 200）且询问次数很多的场景。

Dijkstra算法#

朴素版dijkstra算法#

核心思想（贪心）： 把点分成两类——“已经确定最短距离”的集合 S 和”尚未确定”的集合 T。每一步从 T 中选出当前 dist 最小的点 t，宣布它的最短距离已经确定，然后用 t 去”松弛”它的所有邻居。

为什么可以贪心？ 因为所有边权都是正数，任何经过其他点绕到 t 的路径都不可能比当前直接到 t 的距离更短（绕路只会增加距离），所以当前最小的 dist[t] 就是 t 的最终答案。

具体步骤： 初始化起点距离为 0，其他点到起点的距离设为无穷大；之后迭代 n 次，每次找出不在集合 S 中、距离起点最近的点 t，把它加入 S，并用它更新所有邻居的最短距离（dist[j] = min(dist[j], dist[t] + g[t][j])）。n 轮之后所有点的最短距离都确定下来。

复杂度： 每轮 O(n) 找最小点、O(n) 更新邻居，共 n 轮，总复杂度 O(n²)，适合稠密图（用邻接矩阵存储）。

给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环，所有 边权均为正值。 请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 -1。

输入格式#

第一行包含整数 n 和 m。 接下来 m 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之间存在一条有向边，边长为 z。

输出格式#

输出一个整数，表示 1 号点到 n 号点的最短距离。 如果路径不存在，则输出 -1。

数据范围#

  • 1 ≤ n ≤ 500
  • 1 ≤ m ≤ 10⁵
  • 图中涉及边长均不超过 10000。
import java.util.*;
import java.io.*;
public class Main {
    static int n, m;
    static 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 dijkstra() {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        for (int i = 0; i < n; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            }
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
        //因为是取最小值，而起点无法到达的点的距离一直为INF，更新之后则为INF + N（N为正数），最后取最小值还是INF
        if (dist[n] == INF) {


            return -1;


        }


        return dist[n];
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        Arrays.stream(g).forEach(row -> Arrays.fill(row,INF));
        while (m-- > 0) {
            String[] abc = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abc[0]);
            int b = Integer.parseInt(abc[1]);
            int c = Integer.parseInt(abc[2]);
            //因为是有向图并且存在重边和环，所以只需要保留最短的那条边即可
            g[a][b] = Math.min(g[a][b], c);
        }
        int j = dijkstra();
        System.out.print(j);
    }
}

Dijkstra算法(堆优化版)#

优化点： 朴素版每一轮都要 O(n) 扫描全部点来找”dist 最小的未确定点”，这是主要瓶颈。堆优化版改用**小根堆（PriorityQueue）**维护”候选点及其当前距离”：每次 O(log n) 取出堆顶（当前 dist 最小的点），再用邻接表遍历它的所有出边做松弛，松弛成功就把邻居的新距离压入堆。

实现细节：

  • 一个点可能被多次压入堆（每次它的 dist 变小都会入堆一次），因此出堆时要检查 st 标记：如果这个点早已确定过最短距离，直接跳过（if (st[v]) continue;）。
  • 稀疏图下每个点入堆次数有限，总复杂度约 O(m log m)，通常写作 O(m log n)；当 m 远小于 n² 时远快于朴素版。
import java.util.*;
import java.io.*;
public class Main {
    static int n, m;
    static int N = 510;
    static int idx;
    static final int INF = 0x3f3f3f3f;
    static int[] h = new int[N],e = new int[N],ne = new int[N],w = new int[N];//使用邻接表存储稀疏图，w数组存储边权
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
  static void add(int a,int b,int c){
        e[idx] = b;w[idx] = c; ne[idx] = h[a];h[a] = idx++;
    }
    static int dijkstra() {
        Arrays.fill(dist, INF);
        dist[1] = 0;
        // 小根堆：Node{vertex, dist}
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.d));
        pq.offer(new Node(1,0));
        while(!pq.isEmpty()){
            Node n = pq.poll();
            if(st[n.v]) continue;
            for(int i = h[t];i!= -1;i = ne[i]){
                int j = e[i];
                if(dist[j] > n.d + w[i]){
                    dist[j] = n.d + w[i];
                    pq.offer(dist[j],j);
                }
            }
        }
        if (dist[n] == INF) {
            return -1;
        }
        return dist[n];
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        Arrays.fill(h,-1);
        while (m-- > 0) {
            String[] abc = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abc[0]);
            int b = Integer.parseInt(abc[1]);
            int c = Integer.parseInt(abc[2]);
            add(a,b,c);
        }
        int j = dijkstra();
        System.out.print(j);
    }
    static class Node {
        int v, d;
        Node(int v, int d) { this.v = v; this.d = d; }
    }
}

Bellman-Ford算法#

Bellman-Ford 的核心操作是”松弛”（relax）： 对每条边 (a → b, 权 w)，尝试用 dist[a] + w 更新 dist[b]，即 dist[b] = min(dist[b], dist[a] + w)。

算法流程： 第一重循环迭代 n 次，第二重循环遍历所有边并逐一松弛。边的存储方式没有限制（使用邻接表，邻接矩阵，结构体都可以，只需要保证能够遍历所有的边）。循环结束后，对所有边一定满足 dist[b] ≤ dist[a] + w，这个不等式就是三角不等式。

迭代 k 次的含义： 从起点出发经过不超过 k 条边到达各点的最短距离。因为每做一轮松弛，“最短路经过的边数”最多向前推进一条，所以 k 轮之后得到的就是”最多经过 k 条边”的最短路。

为什么需要 backup 数组？ 第 k 轮松弛必须只用第 k-1 轮的结果。如果边遍历边用本轮刚更新的 dist 继续松弛，就相当于一轮之内”连续走多条边”（串联更新），破坏了”k 轮 = 最多 k 条边”的语义，所以每轮开始前要备份上一轮的 dist。

判负环： 如果第 n 次迭代的时候又更新了某些边的话，就说明存在一条负环——因为从起点到任意点的最短路最多经过 n-1 条边，第 n 轮还在变短，只能说明路径上有环让距离可以无限变小。

有边数限制的最短路#

给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环，边权可能为负数。 请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 "impossible"。 注意：图中 可能存在负权回路。

输入格式#

第一行包含三个整数 n，m，k。 接下来 m 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之间存在一条有向边，边长为 z。

输出格式#

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。 如果不存在满足条件的路径，则输出 "impossible"。

数据范围#

  • 1 ≤ n, k ≤ 500
  • 1 ≤ m ≤ 10000
  • 任意边长的绝对值不超过 10000
import java.util.*;
import java.io.*;
public class Main{
    static int n,m,k;
    static int N = 510,M=100010;
    static int[] dist = new int[N], backup = new int[N];
    static Edge[] edges = new Edge[M];
    static int INF = 0x3f3f3f3f;
    static class Edge {
        int a,b,w;
        Edge(int a,int b, int w){
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    public static int Bellman_Ford(){
        Arrays.fill(dist,INF);
        dist[1] = 0;
        for(int i = 0;i < k;i++ ){
            //备份
            System.arraycopy(dist, 0, backup, 0, n + 1); // Java 版 memcpy
            for(int j = 0;j < m ;j++){
                int a = edges[j].a,b = edges[j].b,w= edges[j].w;
                dist[b] = Math.min(dist[b],backup[a] + w);
            }
        }
        if(dist[n] > INF / 2){
            System.out.print("impossible");
            return -1;
        }
        return dist[n];
//        Arrays.fill(dist, INF);
//        dist[1] = 0;
//        // 最多 k 条边 → 迭代 k 轮
//        for (int i = 0; i < k; i++) {
//            System.arraycopy(dist, 0, backup, 0, n + 1); // Java 版 memcpy
//            for (int j = 0; j < m; j++) {
//                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
//                // 用上一轮备份更新当前轮
//                if (backup[a] != INF && dist[b] > backup[a] + w)
//                    dist[b] = backup[a] + w;
//            }
//        }
//        return dist[n] > INF / 2 ? -1 : dist[n];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nmk = br.readLine().trim().split("\\s+");
        n= Integer.parseInt(nmk[0]);
        m = Integer.parseInt(nmk[1]);
        k = Integer.parseInt(nmk[2]);
        for(int i = 0;i < m;i++){
            String[] abw = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abw[0]), b = Integer.parseInt(abw[1]),w= Integer.parseInt(abw[2]);
            edges[i] = new Edge(a,b,w);
        }
        int j = Bellman_Ford();
        System.out.print(j);


    }
}

SPFA算法#

SPFA算法是基于Bellman_Ford算法来优化的，其优化的点在于Bellman_Ford算法的最后一步。Bellman_Ford算法的最后一步是拿每一个点去更新dist

但是每一次更新并不是有效的，即每一次更新可能有的点的距离没变小。 SPFA在此基础上添加了一个规律——只有一个点的前缀变小了，这个点的dist才会变小。这样我们就只需要将已经变小的点加入队列，然后取出队头来更新其他点的距离，如果有其他点的距离变化就继续加入队列，直至队空。

具体流程： 起点入队并标记 st；每次取出队头 t（并取消标记），遍历 t 的所有出边做松弛；若邻居 j 的 dist 被更新变小，且 j 不在队列中，就把 j 入队并标记，防止同一个点重复入队。st 数组在这里表示”该点当前是否在队列中”，与 Dijkstra 中”是否已确定最短距离”的含义不同。

复杂度与适用性： 平均 O(m)，最坏 O(nm)（可能被特殊数据卡）。SPFA 能处理负权边，但不能处理负环——负环上的距离会无限变小，队列永远空不了。实际比赛中”存在负权边 + 图较稀疏”时通常用 SPFA，否则用堆优化 Dijkstra。

import java.util.*;
import java.io.*;
public class Main {
    static int n, m;
    static int N = 510;
    static int idx;
    static final int INF = 0x3f3f3f3f;
    static int[] h = new int[N],e = new int[N],ne = new int[N],w = new int[N];//使用邻接表存储稀疏图，w数组存储边权
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static void add(int a,int b,int c){
        e[idx] = b;w[idx] = c; ne[idx] = h[a];h[a] = idx++;
    }
    static int spfa() {
        Arrays.fill(dist,INF);
        dist[1] = 0;
        LinkedList<Integer> q = new LinkedList<>();
        q.offer(1);
        st[1] = true;//标志当前点是否在队列当中，防止存储重复的点
        while(!q.isEmpty()){
            int t =  q.poll();
            st[t] = false;
            for(int i = h[t];i != -1;i = ne[i]){
                int j = e[i];
                if(dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }


        }
        if(dist[n] == INF) return -1;
        return dist[n];
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        Arrays.fill(h,-1);
        while (m-- > 0) {
            String[] abc = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abc[0]);
            int b = Integer.parseInt(abc[1]);
            int c = Integer.parseInt(abc[2]);
            add(a,b,c);
        }
        int j = spfa();
        System.out.print(j);
    }
}

SPFA判断负环#

spfa判负环#

给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环，边权可能为负数。 请你判断图中 是否存在负权回路。

输入格式#

第一行包含整数 n 和 m。 接下来 m 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之间存在一条有向边，边长为 z。

输出格式#

如果图中存在负权回路，则输出 "Yes"，否则输出 "No"。

数据范围#

  • 1 ≤ n ≤ 2000
  • 1 ≤ m ≤ 10000
  • 图中涉及边长绝对值均不超过 10000
import java.util.*;
import java.io.*;
public class Main {
    static int n, m;
    static int N = 510;
    static int idx;
    static final int INF = 0x3f3f3f3f;
    static int[] h = new int[N],e = new int[N],ne = new int[N],w = new int[N];//使用邻接表存储稀疏图，w数组存储边权
    static int[] dist = new int[N],cnt = new int[N];//多维护一个cnt数组，用于记录到j点的最短路所经过的边数
    static boolean[] st = new boolean[N];
    static void add(int a,int b,int c){
        e[idx] = b;w[idx] = c; ne[idx] = h[a];h[a] = idx++;
    }
    static boolean spfa() {
        Arrays.fill(dist,INF);
        dist[1] = 0;
        LinkedList<Integer> q = new LinkedList<>();
        //因为需要判断整个图中是否存在负环，所以加入队列中的点不止有1，而是把所有点都加入队列中
        for (int i = 1; i <= n; i++) {
            st[i] = true;
            q.offer(i);
        }
        st[1] = true;//标志当前点是否在队列当中，防止存储重复的点
        while(!q.isEmpty()){
            int t =  q.poll();
            st[t] = false;
            for(int i = h[t];i != -1;i = ne[i]){
                int j = e[i];
                if(dist[j] > dist[t] + w[i]){
                    dist[j] = dist[t] + w[i];
                    cnt[j] = cnt[t] +1;//每次更新最短距离时+1
                    if(cnt[j] >= n ) return true; //若边数大于n就可以断定存在负环
                    if(!st[j]){
                        q.offer(j);
                        st[j] = true;
                    }
                }
            }


        }
        return false;
    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        Arrays.fill(h,-1);
        while (m-- > 0) {
            String[] abc = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abc[0]);
            int b = Integer.parseInt(abc[1]);
            int c = Integer.parseInt(abc[2]);
            add(a,b,c);
        }
        boolean j = spfa();
        System.out.print(j?"YES":"NO");
    }
}

==对于使用cnt[j] >= n就可以断定存在负环的解释：==

==当cnt[j] >= n时说明从1到j这个点的最短路经过了至少n条边，n条边有n+1个点，但是图中一共就n个点==

==根据抽屉原理可知有两个点的编号是重复的，即存在i - > … -> i这样路径的环，而重复出现的i说明每次经过i都更新了最短距离，这就说明i - > … -> i是个负环，不然距离不会变小==

为什么判负环时要先把所有点都入队？ 起点固定为 1 时，只能发现”从 1 出发能到达”的负环；而题目要求判断整个图中是否存在负环，负环可能藏在从 1 走不到的连通块里。把所有点初始都放入队列，相当于从每个点同时开始松弛，这样图中的任何负环都能被发现。

cnt 数组的含义： 记录”当前到 j 的最短路经过了多少条边”。每次成功松弛（dist[j] 变小）时执行 cnt[j] = cnt[t] + 1，一旦某个点的 cnt ≥ n，按上面的抽屉原理就断定存在负环，立即返回。

Floyd算法#

Floyd 求的是多源最短路： 一次预处理，求出任意两点之间的最短距离，之后每次询问都是 O(1)。适合 n 较小（如 n ≤ 200）、询问次数很多的场景。

核心是动态规划： 设 d[k][i][j] 表示”只允许经过编号 ≤ k 的中间点”时，i 到 j 的最短距离。状态转移：

d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])

即”要么不经过点 k，要么经过点 k（先 i → k 再 k → j）“。第一维可以用滚动数组优化掉，就成了代码中的三重循环：d[i][j] = min(d[i][j], d[i][k] + d[k][j])。

为什么 k 必须放在最外层？ 状态定义要求”允许经过的中间点编号 ≤ k”，也就是说在把点 k 加入可经过集合之前，所有”只经过编号 < k 的点”的路径都必须先算好。若把 k 放在内层，就会出现”用尚未更新完成的距离去更新”、甚至把经过 k 的路径又拿去参与别的含 k 路径的更新，导致结果错误。

初始化： d[i][i] = 0；有边则取最小边权（重边取 min）；无边为 INF。判断不可达时用 d[a][b] > INF / 2 而不是 == INF，因为负权边可能让 INF 被”略微更新”，但仍远大于任何真实的最短距离。

Folyd求最短路#

给定一个 n 个点 m 条边的有向图，图中 可能存在重边和自环，边权可能为负数。 再给定 k 个询问，每个询问包含两个整数 x 和 y，表示查询从点 x 到点 y 的最短距离，如果路径不存在，则输出 "impossible"。 数据保证图中不存在负权回路。

输入格式#

第一行包含三个整数 n，m，k。 接下来 m 行，每行包含三个整数 x，y，z，表示点 x 和点 y 之间存在一条有向边，边长为 z。 接下来 k 行，每行包含两个整数 x，y，表示询问点 x 到点 y 的最短距离。

输出格式#

共 k 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 "impossible"。

数据范围#

  • 1 ≤ n ≤ 200
  • 1 ≤ k ≤ n
  • 1 ≤ m ≤ 20000
  • 图中涉及边长绝对值不超过 10000
import java.util.*;
import java.io.*;
public class Main{
    static int N = 210;
    static int INF = 0x3f3f3f3f;
    static int n,m,q;
    static int[][] d = new int[N][N];
    static void Floyd(){
        for(int k = 1;k <= n;k++){
            for(int i = 1;i <=n;i++){
                for(int j = 1;j <=n;j++){
                    d[i][j] = Math.min(d[i][j],d[i][k] + d[k][j]);
                }
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] nmq = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nmq[0]);
        m = Integer.parseInt(nmq[1]);
        q = Integer.parseInt(nmq[2]);
        for(int i = 1;i <=n ;i++){
            for(int j =1;j<=n;j++){
                if(j == i) d[i][j] = 0;
                else d[i][j] = INF;
            }
        }
        while(m-- > 0){
            String[] abw = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abw[0]);
            int b = Integer.parseInt(abw[1]);
            int w = Integer.parseInt(abw[2]);
            d[a][b] = Math.min(d[a][b],w);
        }
        Floyd();
        while(q -- >0){
            String[] ab = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(ab[0]);
            int b = Integer.parseInt(ab[1]);
            if(d[a][b] > INF / 2){
                bw.append("impossile\n");
            }else{
                bw.append(d[a][b] + "\n");
            }
        }
        bw.flush();
    }
}

最小生成树#

在图论中，最小生成树（Minimum Spanning Tree, MST） 是指在一个加权连通图中，选择一些边连接所有的顶点，使得这些边的总权重最小，且不形成回路（即构成一棵树）。

回顾树的性质： n 个点的树恰好有 n-1 条边、连通且无环。所以 MST 的目标就是从 m 条边中选出 n-1 条，连通所有点且权值和最小。

正确性基石——割性质（cut property）： 把图的点集任意分成两个集合（称为一个”割”），跨越这两个集合的所有边中，权值最小的那条边一定属于某棵最小生成树。Prim 和 Kruskal 每一步的贪心选边，本质上都是在反复使用这条性质，因此”每一步局部最优”最终能推出”全局最优”。

解决 MST 问题最经典的有两大算法：Prim（普里姆）算法和 Kruskal（克鲁斯卡尔）算法。

Prim算法#

核心思想：从任意根开始，每次把离当前树最近的一个点拉进来，直到所有点都在树里。

即从任意点开始为根，设定一个集合（这个集合表示在连通块中的点），遍历n次，每次找出不在集合中的距离集合最近的点并使用这个点来更新其他不在集合中的点的最小距离，最后将自身加入集合。

Prim 与 Dijkstra 的异同： 两者代码结构几乎一样，但 dist 的含义不同——Dijkstra 的 dist 是”到源点的最短距离”，Prim 的 dist 是”到当前生成树集合的最近一条边的权值”；且 Prim 是”先累加答案再更新”，Dijkstra 是”取出后直接确定”。

如何判断 MST 不存在？ 若第 i（i > 0）轮选点时，最近点的 dist[t] 仍为 INF，说明剩余的点与生成树完全不连通，图不连通，MST 不存在，输出 “impossible”。

  • 贪心：局部最优 ⇒ 全局最优（由割性质保证）
  • 数据结构：
    • 邻接矩阵（朴素版，稠密图）；或邻接表 + 小根堆（堆优化版，稀疏图）
    • 小根堆（PriorityQueue）存 (顶点, 到树距离)
    • vis[] 标记已入树顶点
  • 复杂度：朴素版 O(n²)；堆优化版 O((V + E) log V) ≈ O(E log V)
  • 朴素版

给定一个 n 个点 m 条边的无向图，图中 可能存在重边和自环，边权可能为负数。 求 最小生成树的树边权重之和，如果最小生成树不存在则输出 "impossible"。

给定一张边带权的无向图 G=(V, E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。 由 V 的全部 n 个顶点和 E 中 n-1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的 最小生成树。

输入格式#

第一行包含两个整数 n 和 m。 接下来 m 行，每行包含三个整数 u, v, w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式#

共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和； 如果最小生成树不存在则输出 "impossible"。

数据范围#

  • 1 ≤ n ≤ 500
  • 1 ≤ m ≤ 10⁵
  • 图中涉及边的边权的绝对值均不超过 10000
import java.util.*;
import java.io.*;
public class Main{
    static int N = 510;
    static int[][] g = new int[N][N];
    static boolean[] st = new boolean[N];
    static int[] dist = new int[N];
    static int INF = 0x3f3f3f3f,n,m;
    static int prim(){
        Arrays.fill(dist,INF);
        int res = 0;
        for(int i = 0;i <n;i++){
            int t = -1;
            for(int j = 1;j <=n;j++){
                if(!st[j] && (t == -1 || dist[t] >dist[j])){
                    t = j;
                }
            }
            if(i > 0 && dist[t] == INF) return INF;//不是第一个点并且最小距离为INF那么这个图并不是连通的直接返回INF
            if(i > 0) res += dist[t];
            //满足条件，且不是第一个点就加上这条边，并使用这条边更新其他不在st中点的最短距离，最后将这点加入连通块中
            for(int j = 1;j <=n;j++){
                dist[j] = Math.min(dist[j],g[t][j]);
            }
            st[t] = true;
        }
        return res;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        Arrays.stream(g).forEach(row -> Arrays.fill(row,INF));
        while(m-- >0){
            String[] abc = br.readLine().trim().split("\\s+");
            int a = Integer.parseInt(abc[0]);
            int b = Integer.parseInt(abc[1]);
            int c = Integer.parseInt(abc[2]);
            g[a][b] = g[b][a] = Math.min(g[a][b],c);//无向图存储a到b的边和b到a的边
        }
        int t = prim();


        if(t == INF){
            System.out.print("impossible");
        }else{
            System.out.print(t);
        }
    }


}

堆优化版（参考dijkstra堆优化版）

Kruskal算法#

按边权 从小到大 排序，贪心选边，用 并查集 判环，直到选出 n-1 条边。

为什么贪心选边是对的？ 仍然由割性质保证：当前最小的边若连接两个不同的连通块，它就是”跨越某个割的最小边”，一定属于某棵 MST；若两个端点已在同一连通块，加入它会成环，必须跳过。

将所有边按权重从小到大排序（这一步是瓶颈）快排O(mlogm)，但是常数很小。

然后判断ab这条边的两个端点a和b是否在一个连通块中，若是不在就将这条边加入连通块即可（合并两个连通块、累加权值、计数 +1），直到选出 n-1 条边为止。最后若选出的边数不足 n-1，说明图不连通，MST 不存在。

关于并查集： 初始化时每个点自成一个集合；find(x) 负责寻找 x 所在集合的代表元（同时做路径压缩）。判环的原理正是”若一条边的两个端点已经连通，再加这条边就必然形成回路”。

kruskal算法适用大部分的稀疏图，建议使用此算法，而不是堆优化版的prim，因为麻烦——Kruskal 只需”排序 + 并查集”，实现简单、常数小。

import java.util.*;
import java.io.*;
public class Main{
    static int n,m;
    static int[] p = new int[200010];
    static Edge[] edges = new Edge[200010];
    static class Edge{
        int a,b,w;
        Edge(int a,int b,int w){
            this.a = a;
            this.b = b;
            this.w = w;
        }
        int getW(){
           return this.w;
        }
    }
    static int find(int x){
        if(p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);
        for(int i = 0;i< m;i++){
            int a,b,w;
            String[] abw = br.readLine().trim().split("\\s+");


            a = Integer.parseInt(abw[0]);
            b = Integer.parseInt(abw[1]);
            w = Integer.parseInt(abw[2]);
            edges[i] = new Edge(a,b,w);
        }
        Arrays.sort(edges,0,m-1,Comparator.comparingInt(Edge::getW));
        for(int i = 1;i <= n;i++){
            p[i] = i;
        }
        int res = 0;
        int cnt = 0;
        for(int i = 0;i< m;i++){
            int a = edges[i].a;
            int b = edges[i].b;
            int w = edges[i].w;
            a = find(a);
            b = find(b);
            if(a!=b){
                p[a] = b;
                res += w;
                cnt ++;
            }
        }
        if(cnt < n-1){
            System.out.print("impossible");
        }else{
            System.out.print(res);
        }
    }


}
分享

如果这篇文章对你有帮助，欢迎分享给更多人！

最短路算法和最小生成树
https://blogstella.xyz/posts/算法入门之最短路算法和最小生成树/
作者
Stella
发布于
2026-03-12
许可协议
CC BY-NC-SA 4.0

部分信息可能已经过时

排序与二分查找
Writing a Blog Post
相关文章 智能推荐
1
Trie树
算法 Trie 字典树入门，讲解如何利用公共前缀高效存储与查找字符串集合，附插入与查询的 Java 实现。
2
前缀和与差分
算法 前缀和与差分的概念与 Java 实现，涵盖一维前缀和、一维差分与二维差分，将区间查询与区间修改转化为 O(1) 的单点操作。
3
DFS和BFS
算法 深度优先搜索与广度优先搜索入门，包括全排列、N 皇后、单词搜索与走迷宫等经典例题的讲解与 Java 实现。
4
双指针算法与位运算
算法 双指针算法与位运算的核心思想与例题，包括用双指针将 O(n²) 暴力优化为 O(n) 的常见套路，以及 lowbit 等常用位运算技巧。
5
KMP算法
算法 KMP 字符串匹配算法详解，从朴素做法出发引出 next 跳转表，说明如何利用已匹配的信息避免重复比较。
随机文章 随机推荐
1
数据结构之哈希表
数据结构 2026-03-31
2
高斯消元
算法 2026-03-31
3
数据结构之链表栈和队列
数据结构 2026-03-31
4
MDX Syntax Guide
Guides 2026-08-08
5
组合计数
算法 2026-03-31
© 2026 Stella. All Rights Reserved. / RSS / Atom / Sitemap
Powered by Astro & Mizuki  Version 9.0

目录