最小生成樹定義：

? ? ? ? 給定一張邊帶權的無向圖 G=(V,E)，其中 V 表示圖中點的集合，E 表示圖中邊的集合。

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

最小生成樹應用場景：

? ? ? ? 例如在城市規劃中，有 n 座城市，需要修建高速公路來連通各個城市，如何設計可使得路程修建總距離最短。可以抽象為，當前有個 n 個點的無向圖，每個點之間都有一條連線，從中找出 n-1 條邊，使得所有的點都在一個集合中，且集合中所有邊的權值加起來最小。

? ? ? ? 也可廣泛的應用于通信，電路，航線等等類似的問題。

最小生成樹其他算法?最小生成樹---樸素Prim算法，堆優化版Prim算法-CSDN博客

---

?Kruskal算法

使用到并查集并查集（基本原理+示例）-CSDN博客?

算法思路：

S：已加入最小生成樹的點的集合

偽代碼：

1.將所有的邊按權重從小到大進行排序（點之間是雙向的，但只需要存儲一個方向的邊）

2.枚舉每一條邊 a -> b 權重c

? ? ? ? if a，b不聯通

? ? ? ? ? ? ? ? 將這條邊加入集合S （使用到并查集的方法）

?最小生成樹的題（都來源acwing）：

1138. 城市公交網建設問題 - AcWing題庫?（數據范圍小，prim也可使用）

1147. 構造完全圖 - AcWing題庫

最小生成樹的?題庫 - AcWing

例題：??1139. 最優布線問題 - AcWing題庫

學校有?n?臺計算機，編號是?1～n，為了方便數據傳輸，現要將它們用數據線連接起來，同一條數據線中數據的傳輸可以是?雙向?的。

兩臺計算機被連接是指它們有數據線連接。

由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。

當然，如果將任意兩臺計算機都用數據線連接，費用將是相當龐大的。

為了節省費用，我們采用數據的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉）來實現與另一臺計算機的連接。

現在由你負責連接這些計算機，任務是使任意兩臺計算機都連通（不管是直接的或間接的）。

輸入格式

第一行為整數?n，表示計算機的數目。

此后的?n?行，每行?n?個整數，輸入一個對角線上全部是0的?對稱矩陣。
其中第?x+1 行?y?列的整數表示直接連接第?x?臺計算機和第?y?臺計算機的費用。

輸出格式

一個整數，表示最小的連接費用。

數據范圍

2≤n≤100,
連接任意兩臺計算機的費用均是非負整數且不超過10000。

輸入樣例：

3
0 1 2
1 0 1
2 1 0

輸出樣例：

2

import java.io.*;
import java.util.*;class Main{static int N = 110;static int n,m,res;static int[] p = new int[N];static Queue<PII> q = new PriorityQueue<>();public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));n = Integer.parseInt(in.readLine());for(int i=1;i<=n;i++){p[i] = i; // 初始化p[]，一個點一個集合String[] s = in.readLine().split(" ");for(int j=1;j<i;j++){q.add(new PII(i,j,Integer.parseInt(s[j-1]))); // 只讀取左下半的數據}}// kruskal算法while(!q.isEmpty()){ // 讀取所有的邊PII t = q.poll();int a = t.a, b = t.b, c = t.c;if(find(a)!=find(b)){ // 如果不在一個集合p[find(a)] = find(b); // 加到一個集合res += c; // 加上權重}}System.out.println(res);}// 找集合的根節點public static int find(int u){if(p[u]!=u) p[u] = find(p[u]);return p[u];}
}
// 存儲邊
class PII implements Comparable<PII>{int a;int b;int c;public PII(int a,int b,int c){this.a = a;this.b = b;this.c = c;}public int compareTo(PII i){return this.c-i.c;}
}