【圖論常見模板題】4種最短路解法和2種最小生成樹解法

樸素版Dijkstra

• O(n^2)，適用於稠密圖，使用鄰接矩陣

1. 每一次找出一個離源點最近的點
2. 將這個點加入最短路集合中
3. 使用這個點去更新其他點到源點的距離

堆優化版Dijkstra

• O(mlogm)，適用於稀疏圖，使用鄰接錶

1. 每一次從小根堆中獲得離源點最近的點
2. 將這個點加入到最短路集合中
3. 使用這個點去更新從這個點出發可以到達的點到源點的距離

Bellman-Ford

• O(nm)，常用於有限制次數的最短路，使用Edge結構體

1. 將所有的點加入到隊列中
2. 更新k次，每一次都將所有的點進行更新

Spfa

• 最好O(n)，最壞O(nm)，可以判斷是否出現負權回路

1. 將源點加入到隊列中
2. 使用源點去更新其他的點，並將被更新過的點放入隊列中，下一輪去更新其他的點。其中為了保證相同點不同在同一輪中不被重複放入隊列中，可以使用boolean[]

Kruskal

• O(mlogm)，適用於稀疏圖，使用Edge結構體

1. 將所有邊按照權重排昇序
2. 從小到大選擇邊加入到最小生成樹中，如果點所屬集合不同，就將不同點加入到同一個集合中，最終形成一個集合

Prim

• O(n^2)，適用於稠密圖，使用鄰接矩陣

1. 每一次找出一個離源點集合最近的點
2. 將這個點加入最小生成樹集合中
3. 使用這個點去更新其他點到源點集合的距離

Dijkstra求最短路

給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。

請你求出 11 號點到 nn 號點的最短距離，如果無法從 11 號點走到 nn 號點，則輸出 −1−1。

• 輸入格式

第一行包含整數 nn 和 mm。

接下來 mm 行每行包含三個整數 x,y,zx,y,z，錶示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz。

• 輸出格式

輸出一個整數，錶示 11 號點到 nn 號點的最短距離。

如果路徑不存在，則輸出 −1−1。

• 數據範圍

1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
圖中涉及邊長均不超過10000。

• 輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

• 輸出樣例：

3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    
    final static int INF = 0x3f3f3f3f;
    static int n, m;
    static int[][] g;
    public static void main(String[] args) throws IOException {
    
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] cur = in.readLine().split(" ");
        n = Integer.parseInt(cur[0]);
        m = Integer.parseInt(cur[1]);
        g = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i ++) {
    
            Arrays.fill(g[i], INF);
        }
        for (int i = 0; i < m; i ++) {
    
            String[] str = in.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            int c = Integer.parseInt(str[2]);
            g[a][b] = Math.min(g[a][b], c);
        }
        Dijkstra();
    }
    public static void Dijkstra() {
    
        boolean[] vis = new boolean[n + 1];
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;
        for (int i = 1; i <= n; i ++) {
    
            int t = -1;
            for (int j = 1; j <= n; j ++) {
    
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
    
                    t = j;
                }
            }
            vis[t] = true;
            for (int j = 1; j <= n; j ++) {
    
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
        if (dist[n] == INF) System.out.println("-1");
        else System.out.println(dist[n]);
    }
}

堆優化版的Dijkstra求最短路

給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為非負值。

請你求出 11 號點到 nn 號點的最短距離，如果無法從 11 號點走到 nn 號點，則輸出 −1−1。

• 輸入格式

第一行包含整數 nn 和 mm。

接下來 mm 行每行包含三個整數 x,y,zx,y,z，錶示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz。

• 輸出格式

輸出一個整數，錶示 11 號點到 nn 號點的最短距離。

如果路徑不存在，則輸出 −1−1。

• 數據範圍

1≤n,m≤1.5×1051≤n,m≤1.5×105,
圖中涉及邊長均不小於 00，且不超過 1000010000。
數據保證：如果最短路存在，則最短路的長度不超過 109109。

• 輸入樣例：

3 3
1 2 2
2 3 1
1 3 4

• 輸出樣例：

3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

// 堆優化版Dijkstra
public class Main {
    
    static int n, m;
    static int N = 150010;
    // idx錶示當前為第幾個節點
    // he[i]錶示以i節點為開頭的鏈錶的頭結點是第幾條邊，e[idx]錶示第idx條有向邊指向哪一個頂點
    // ne[idx]錶示第idx錶有向邊指向鏈錶的節點，w[idx]錶示第idx條有向邊的邊權重
    static int idx = 0;
    static int[] he = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static void add(int a, int b, int c) {
    
        e[idx] = b; w[idx] = c; ne[idx] = he[a]; he[a] = idx ++;
    }
    static int[] dist = new int[N];
    static boolean[] vis = new boolean[N];
    static int INF = 0x3f3f3f3f;
    public static void main(String[] args) throws IOException {
    
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] cur = in.readLine().split(" ");
        n = Integer.parseInt(cur[0]);
        m = Integer.parseInt(cur[1]);
        for (int i = 0; i <= n; i ++) {
    
            he[i] = -1;
        }
        for (int i = 0; i < m; i ++) {
    
            String[] str = in.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            int c = Integer.parseInt(str[2]);
            add(a, b, c);
        }
        Dijkstra();
    }
    public static void Dijkstra() {
    
        for (int i = 0; i <= n; i ++) {
    
            dist[i] = INF;
        }
        dist[1] = 0;
        PriorityQueue<int[]> q = new PriorityQueue<>(new Comparator<int[]>() {
    
            @Override
            public int compare(int[] a, int[] b) {
    
                return a[0] - b[0];
            }
        });
        // int[]第一個參數是頂點到1號的距離，第二個參數是頂點編號
        q.add(new int[]{
    0, 1});
        while (!q.isEmpty()) {
    
            int[] top = q.poll();
            int distance = top[0], vertex = top[1];
            if (vis[vertex]) continue;
            vis[vertex] = true;
            // 遍曆以vertex頂點開頭的所有的有向邊，i是有向邊的編號
            for (int i = he[vertex]; i != -1; i = ne[i]) {
    
                int j = e[i];
                if (distance + w[i] < dist[j]) {
    
                    dist[j] = distance + w[i];
                    q.add(new int[]{
    dist[j], j});
                }
            }
        }
        if (dist[n] == INF) System.out.println("-1");
        else System.out.println(dist[n]);
    }
}

Bellman-ford求最短路

給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你求出從 11 號點到 nn 號點的最多經過 kk 條邊的最短距離，如果無法從 11 號點走到 nn 號點，輸出 impossible。

注意：圖中可能 存在負權回路 。

• 輸入格式

第一行包含三個整數 n,m,kn,m,k。

接下來 mm 行，每行包含三個整數 x,y,zx,y,z，錶示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz。

• 輸出格式

輸出一個整數，錶示從 11 號點到 nn 號點的最多經過 kk 條邊的最短距離。

如果不存在滿足條件的路徑，則輸出 impossible。

• 數據範圍

1≤n,k≤5001≤n,k≤500,
1≤m≤100001≤m≤10000,
任意邊長的絕對值不超過 1000010000。

• 輸入樣例：

3 3 1
1 2 1
2 3 1
1 3 3

• 輸出樣例：

3

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.List;

public class Main {
    
    private static final int INF = 0x3f3f3f3f;

    static class Edge {
    
        int a, b, c;
        public Edge(int a, int b, int c) {
    
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
    static int N = 510, M = 10010;
    static int n, m, k;
    static List<Edge> list = new ArrayList<>();
    static int[] dist = new int[N];
    public static void main(String[] args) throws IOException {
    
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] cur = in.readLine().split(" ");
        n = Integer.parseInt(cur[0]);
        m = Integer.parseInt(cur[1]);
        k = Integer.parseInt(cur[2]);
        for (int i = 0; i < m; i ++) {
    
            String[] str = in.readLine().split(" ");
            int a = Integer.parseInt(str[0]);
            int b = Integer.parseInt(str[1]);
            int c = Integer.parseInt(str[2]);
            list.add(new Edge(a, b, c));
        }
        BellmanFord();
    }
    public static void BellmanFord() {
    
        for (int i = 0; i <= n; i ++) {
    
            dist[i] = INF;
        }
        dist[1] = 0;
        // 進行k次更新
        for (int i = 0; i < k; i ++) {
    
            // 每一次更新不能有連帶效應，所以需要將上一次的dist深拷貝一份
            int[] prev = dist.clone();
            for (Edge edge : list) {
    
                dist[edge.b] = Math.min(dist[edge.b], prev[edge.a] + edge.c);
            }
        }
        if (dist[n] > INF / 2) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
}

Spfa求最短路

給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你求出 11 號點到 nn 號點的最短距離，如果無法從 11 號點走到 nn 號點，則輸出 impossible。

數據保證不存在負權回路。

• 輸入格式

第一行包含整數 nn 和 mm。

接下來 mm 行每行包含三個整數 x,y,zx,y,z，錶示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz。

• 輸出格式

輸出一個整數，錶示 11 號點到 nn 號點的最短距離。

如果路徑不存在，則輸出 impossible。

• 數據範圍

1≤n,m≤1051≤n,m≤105,
圖中涉及邊長絕對值均不超過 1000010000。

• 輸入樣例：

3 3
1 2 5
2 3 -3
1 3 4

• 輸出樣例：

2

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.Deque;  
import java.util.LinkedList;  
import java.util.List;  
  
class Main {
      
    private static final int INF = 0x3f3f3f3f;  
    static int n, m;  
    static int N = 100010;  
    static int[] he = new int[N], e = new int[N], w = new int[N], ne = new int[N];  
    static int idx = 0;  
    static int[] dist = new int[N];  
    static boolean[] vis = new boolean[N];  
    public static void add(int a, int b, int c) {
      
        e[idx] = b; w[idx] = c; ne[idx] = he[a]; he[a] = idx ++;  
    }  
    public static void main(String[] args) throws IOException {
      
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
        String[] cur = in.readLine().split(" ");  
        n = Integer.parseInt(cur[0]);  
        m = Integer.parseInt(cur[1]);  
        for (int i = 0; i <= n; i ++) {
      
            he[i] = -1;  
        }  
        for (int i = 0; i < m; i ++) {
      
            String[] str = in.readLine().split(" ");  
            int a = Integer.parseInt(str[0]);  
            int b = Integer.parseInt(str[1]);  
            int c = Integer.parseInt(str[2]);  
            add(a, b, c);  
        }  
        Spfa();  
    }  
  
    public static void Spfa() {
      
        for (int i = 0; i <= n; i ++) {
      
            dist[i] = INF;  
        }  
        dist[1] = 0;  
        vis[1] = true;  
        Deque<Integer> q = new LinkedList<>();  
        q.add(1);  
        // 使用vis數組是為了防止當前已經加入隊列的節點，無需重複被加入到隊列中 
        // 但是因為一個頂點可能被用於多次更新路徑，所以每一次使用一個頂點更新完路徑之後 
        // 還需要將vis[ver]=false，使得下一次該頂點可以被更新 
        while (!q.isEmpty()) {
      
            int ver = q.pollFirst();  
            vis[ver] = false;  
            for (int i = he[ver]; i != -1; i = ne[i]) {
      
                int j = e[i];  
                if (w[i] + dist[ver] < dist[j]) {
      
                    dist[j] = w[i] + dist[ver];  
                    if (!vis[j]) {
      
                        vis[j] = true;  
                        q.add(j);  
                    }  
                }  
            }  
        }  
        if (dist[n] > INF / 2) System.out.println("impossible");  
        else System.out.println(dist[n]);  
    }  
}

Dijkstra為什不能計算帶有負權值的邊的圖？

• Dijkstra是基於貪心策略的，每一次都選取離當前點最近的點，使用這個點來更新其他點。但是如果圖中的邊有負數的話，那麼當前最近的點可能就不是最好的選擇，而非最近點可能因為負權邊兒時的路徑和不斷减小。
• ![[Pasted image 20220616104956.png]]

Dijkstra和Spfa寫法上的區別？

• Dijkstra和Spfa寫法上雖然很像，但是含義是完全不同的。無論是樸素版的Dijkstra還是堆優化版的Dijkstra，每一次都是先獲取離源點最近並且沒有被更新過的點，然後用這個點去更新其他的路徑。但是Spfa每一次只是將上一次被更新過的點，放入隊列（也可以是其他的數據結構），用這些被更新過的點去更新其他的點。
• 相對而言，基於貪心的Dijkstra更强調局部最優解，而Spfa只在意最終的最短路，所以Spfa算法的整體結構更加松弛。也是因為這樣所以Spfa能够處理負權邊的圖。

Spafa判斷負權回路

給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環， 邊權可能為負數。

請你判斷圖中是否存在負權回路。

• 輸入格式

第一行包含整數 nn 和 mm。

接下來 mm 行每行包含三個整數 x,y,zx,y,z，錶示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz。

• 輸出格式

如果圖中存在負權回路，則輸出 Yes，否則輸出 No。

• 數據範圍

1≤n≤20001≤n≤2000,
1≤m≤100001≤m≤10000,
圖中涉及邊長絕對值均不超過 1000010000。

• 輸入樣例：

3 3
1 2 -1
2 3 4
3 1 -4

• 輸出樣例：

Yes

• 因為m很大，說明邊數很多，因此使用鄰接錶比較好。

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Deque;  
import java.util.LinkedList;  

class Main {
      
    private static final int INF = 0x3f3f3f3f;  
    static int n, m;  
    static int N = 100010;  
    static int[] he = new int[N], e = new int[N], w = new int[N], ne = new int[N];  
    static int idx = 0;  
    static int[] dist = new int[N];  
    static boolean[] vis = new boolean[N];  
    // cnt[i]錶示i頂點到原點的最短路徑的邊數 
    // 如果cnt[i]>=n的話，說明i頂點到原點的最短距離的邊數超過n，那麼至少有一個點被使用了n+1次 
    // 即出現了回路，而正數不可能出現回路，說明圖中出現了負權回路 
    static int[] cnt = new int[N];  
    public static void add(int a, int b, int c) {
      
        e[idx] = b; w[idx] = c; ne[idx] = he[a]; he[a] = idx ++;  
    }  
    public static void main(String[] args) throws IOException {
      
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
        String[] cur = in.readLine().split(" ");  
        n = Integer.parseInt(cur[0]);  
        m = Integer.parseInt(cur[1]);  
        for (int i = 0; i <= n; i ++) {
      
            he[i] = -1;  
        }  
        for (int i = 0; i < m; i ++) {
      
            String[] str = in.readLine().split(" ");  
            int a = Integer.parseInt(str[0]);  
            int b = Integer.parseInt(str[1]);  
            int c = Integer.parseInt(str[2]);  
            add(a, b, c);  
        }  
        if(Spfa()) System.out.println("Yes");  
        else System.out.println("No");  
    }  
    public static boolean Spfa() {
      
		// dist數組初不初始化都可以，因為如果出現負權回路的話，dist[i]是多少都會被更新
		for (int i = 0; i <= n; i ++) {
    
			dist[i] = INF;
		}
        Deque<Integer> q = new LinkedList<>();  
		// 為了避免一個點不能達到負權回路，所以需要將所有的路徑都考慮在內，因此需要將所有頂點都放入隊列中進行檢驗
        for (int i = 1; i <= n; i ++) {
      
            vis[i] = true;  
            q.add(i);  
        }  
        while (!q.isEmpty()) {
      
            int ver = q.pollFirst();  
            vis[ver] = false;  
            for (int i = he[ver]; i != -1; i = ne[i]) {
      
                int j = e[i];  
                if (dist[j] > dist[ver] + w[i]) {
      
                    dist[j] = dist[ver] + w[i];  
                    // 每當j頂點被更新，說明從ver點到j點上的最短路徑多了一條邊 
                    cnt[j] = cnt[ver] + 1;  
                    if (cnt[j] > n) return true;  
                    if (!vis[j]) {
      
                        vis[j] = true;  
                        q.add(j);  
                    }  
                }  
            }  
        }  
        return false;  
    }  
}

• 注意：這面這種寫法只是為了檢驗路徑中是否存在回路，所以並沒有將標准的Spfa計算最短路寫出來。

Floyd求最短路

給定一個 nn 個點 mm 條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數。

再給定 kk 個詢問，每個詢問包含兩個整數 xx 和 yy，錶示查詢從點 xx 到點 yy 的最短距離，如果路徑不存在，則輸出 impossible。

數據保證圖中不存在負權回路。

• 輸入格式

第一行包含三個整數 n,m,kn,m,k。

接下來 mm 行，每行包含三個整數 x,y,zx,y,z，錶示存在一條從點 xx 到點 yy 的有向邊，邊長為 zz。

接下來 kk 行，每行包含兩個整數 x,yx,y，錶示詢問點 xx 到點 yy 的最短距離。

• 輸出格式

共 kk 行，每行輸出一個整數，錶示詢問的結果，若詢問兩點間不存在路徑，則輸出 impossible。

• 數據範圍

1≤n≤2001≤n≤200,
1≤k≤n21≤k≤n2
1≤m≤200001≤m≤20000,
圖中涉及邊長絕對值均不超過 1000010000。

• 輸入樣例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

• 輸出樣例：

impossible
1

[[動態規劃]]

• dp[k][i][j]錶示最短路考慮了k節點作為中間經過節點。
• 遞推公式：dp[k][i][j] = Math.min(dp[k-1][i][j], dp[k-1][i][k]+dp[k-1][k][j])，
  • dp[k-1][i][j]錶示從i到j不經過k節點的最短路徑
  • dp[k-1][i][k]+dp[k-1][k][j]錶示從i到k再到j的最短路徑。
• 由於遞歸公式中dp[k]只和dp[k-1]有關，並且經過計算的dp[k][i][j]會變得更小，不影響最終結果，因此可以省掉一維空間限制。dp[i][j]=Math.min(dp[i][j], dp[i][k]+dp[k][j])，但是循環的順序不能改變，還是要先循環中間節點變量k。

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

class Main {
      
    static int N = 210;  
    static int[][] g = new int[N][N];  
    static int n, m, k;  
    static int INF = 0x3f3f3f3f;  
    public static void main(String[] args) throws IOException {
      
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
        String[] cur = in.readLine().split(" ");  
        n = Integer.parseInt(cur[0]);  
        m = Integer.parseInt(cur[1]);  
        k = Integer.parseInt(cur[2]);  
        // 注意要是用floyd，一定要保證頂點到自己距離為0 
        for (int i = 0; i <= n; i ++) {
      
            for (int j = 0; j <= n; j ++) {
      
                if (i == j) g[i][j] = 0;  
                else g[i][j] = INF;  
            }  
        }  
        for (int i = 0; i < m; i ++) {
      
            String[] str = in.readLine().split(" ");  
            int a = Integer.parseInt(str[0]);  
            int b = Integer.parseInt(str[1]);  
            int c = Integer.parseInt(str[2]);  
            g[a][b] = Math.min(g[a][b], c);  
        }  
        Floyd();  
        while (k -- > 0) {
      
            String[] str = in.readLine().split(" ");  
            int a = Integer.parseInt(str[0]);  
            int b = Integer.parseInt(str[1]);  
            if (g[a][b] == INF) System.out.println("impossible");  
            else System.out.println(g[a][b]);  
        }  
    }  
    public static void Floyd() {
      
        for (int k = 1; k <= n; k ++) {
      
            for (int i = 1; i <= n; i++) {
      
                for (int j = 1; j <= n; j++) {
      
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);  
                }  
            }  
        }  
    }  
}

Kruskal求最小生成樹

給定一個 nn 個點 mm 條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。

求最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

給定一張邊帶權的無向圖 G=(V,E)G=(V,E)，其中 VV 錶示圖中點的集合，EE 錶示圖中邊的集合，n=|V|n=|V|，m=|E|m=|E|。

由 VV 中的全部 nn 個頂點和 EE 中 n−1n−1 條邊構成的無向連通子圖被稱為 GG 的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖 GG 的最小生成樹。

• 輸入格式

第一行包含兩個整數 nn 和 mm。

接下來 mm 行，每行包含三個整數 u,v,wu,v,w，錶示點 uu 和點 vv 之間存在一條權值為 ww 的邊。

• 輸出格式

共一行，若存在最小生成樹，則輸出一個整數，錶示最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

• 數據範圍

1≤n≤1051≤n≤105,
1≤m≤2∗1051≤m≤2∗105,
圖中涉及邊的邊權的絕對值均不超過 10001000。

• 輸入樣例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

• 輸出樣例：

6

[[並查集]]+[[貪心]]

• 將邊的權重進行排序，優先選擇最小權重的邊作為最小生成樹的分支。
• 被選入成為最小生成樹的邊需要被標記已經被選入了，但是不能使用boolean[]進行標記。因為可能出現一個邊已經被選擇了，但是這條邊只是最小生成樹的一棵子樹，之後這棵子樹還要被加入到最小生成樹的另一部分中。如果使用boolean標記的話，一提邊被標記之後就不能在被選擇了，此時就需要使用並查集，將不同的定點所屬的集合能够區分開來。

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.Comparator;  
import java.util.List;

class Main {
      
    static int n, m;  
    static List<Edge> list = new ArrayList<>();  
    static int N = 100010, M = 200010;  
    static boolean[] vis = new boolean[N];  
    static int[] p = new int[N];  
    static class Edge {
      
        int a, b, c;  
        public Edge(int a, int b, int c) {
      
            this.a = a;  
            this.b = b;  
            this.c = c;  
        }  
    }  
    public static void main(String[] args) throws IOException {
      
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
        String[] cur = in.readLine().split(" ");  
        n = Integer.parseInt(cur[0]);  
        m = Integer.parseInt(cur[1]);  
        for (int i = 0; i < m; i ++) {
      
            String[] str = in.readLine().split(" ");  
            int a = Integer.parseInt(str[0]);  
            int b = Integer.parseInt(str[1]);  
            int c = Integer.parseInt(str[2]);  
            list.add(new Edge(a, b, c));  
        }  
        kruskal();  
    }  
  
    public static void kruskal() {
      
        // 初始化並查集 
        for (int i = 0; i <= n; i ++) {
      
            p[i] = i;  
        }  
        Collections.sort(list, new Comparator<Edge>(){
      
            public int compare(Edge a, Edge b) {
      
                return a.c - b.c;  
            }  
        }); 
		// cnt錶示當前最小生成樹中邊的條數
		// 雖然判斷最小生成樹有兩種方式，一種使用邊的條數，一種使用點的個數。由於每一次加入集合中頂點的個數可能是1個或者2個，所以使用統計的邊的方式來進行判定
        int cnt = 0;  
        int ans = 0;  
        for (Edge edge : list) {
      
            int a = edge.a, b = edge.b;  
            // 找到頂點自己所屬的集合，如果頂點所屬集合不同，就將頂點加入到同一個集合中 
            a = find(a);  
            b = find(b);  
            if (a != b) {
      
                p[a] = b;  
                cnt ++;  
                ans += edge.c;  
            }  
        }  
        if (cnt == n - 1) System.out.println(ans);  
        else System.out.println("impossible");  
    }  
  
    public static int find(int x) {
      
        if (x != p[x]) p[x] = find(p[x]);  
        return p[x];  
    }
}

Prim求最小生成樹

給定一個 nn 個點 mm 條邊的無向圖，圖中可能存在重邊和自環，邊權可能為負數。

求最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

給定一張邊帶權的無向圖 G=(V,E)G=(V,E)，其中 VV 錶示圖中點的集合，EE 錶示圖中邊的集合，n=|V|n=|V|，m=|E|m=|E|。

由 VV 中的全部 nn 個頂點和 EE 中 n−1n−1 條邊構成的無向連通子圖被稱為 GG 的一棵生成樹，其中邊的權值之和最小的生成樹被稱為無向圖 GG 的最小生成樹。

• 輸入格式

第一行包含兩個整數 nn 和 mm。

接下來 mm 行，每行包含三個整數 u,v,wu,v,w，錶示點 uu 和點 vv 之間存在一條權值為 ww 的邊。

• 輸出格式

共一行，若存在最小生成樹，則輸出一個整數，錶示最小生成樹的樹邊權重之和，如果最小生成樹不存在則輸出 impossible。

• 數據範圍

1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
圖中涉及邊的邊權的絕對值均不超過 1000010000。

• 輸入樣例：

4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4

• 輸出樣例：

6

[[貪心]]

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  

class Main {
      
    static int n, m;  
    static int N = 510;  
    static int[][] g = new int[N][N];  
    static int INF = 0x3f3f3f3f;  
    static int[] dist = new int[N];  
    static boolean[] vis = new boolean[N];  
    public static void main(String[] args) throws IOException {
      
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));  
        String[] cur = in.readLine().split(" ");  
        n = Integer.parseInt(cur[0]);  
        m = Integer.parseInt(cur[1]);  
        for (int i = 0; i <= n; i ++) {
      
            for (int j = 0; j <= n; j ++) {
      
                if (i == j) g[i][j] = 0;  
                else g[i][j] = INF;  
            }  
        }  
        for (int i = 0; i < m; i ++) {
      
            String[] str = in.readLine().split(" ");  
            int a = Integer.parseInt(str[0]);  
            int b = Integer.parseInt(str[1]);  
            int c = Integer.parseInt(str[2]);  
            g[a][b] = g[b][a] = Math.min(g[a][b], c);  
        }  
        int ans = prim();  
        if (ans == INF) System.out.println("impossible");  
        else System.out.println(ans);  
    }  
    public static int prim() {
      
        // dist錶示的是頂點到最小生成樹組成的集合的距離 
        for (int i = 0; i <= n; i ++) {
      
            dist[i] = INF;  
        }  
        dist[1] = 0;  
        int ans = 0;  
        for (int i = 1; i <= n; i ++) {
      
            int t = -1;  
            for (int j = 1; j <= n; j ++) {
      
                if (!vis[j] && (t == -1 || dist[t] > dist[j])) {
      
                    t = j;  
                }  
            }  
            if (dist[t] == INF) return INF;  
            vis[t] = true;  
            ans += dist[t];  
            for (int j = 1; j <= n; j ++) {
      
                // 使用離連通部分最近的點去更新其他的點 
                if (!vis[j] && dist[j] > g[t][j]) {
      
                    dist[j] = g[t][j];  
                }  
            }  
        }  
        return ans;  
    }  
}

Prim和Dijkstra的比較

• 從寫法上看Prim和樸素版Dijkstra除了在最後使用點更新其他邊不一樣，其餘的部分幾乎一模一樣。但是Prim和Dijkstra含義上最大的不同是Prim每一次選出一個離源點集合（即最小生成樹形成的集合）最近的點。所以每一次更新的時候，dist[j]需要使用g[t][j]來更新。因為此時t在源點集合中，即t錶示的就是源點集合。