昨天的併查集就是為了今天的題目做鋪墊：最小生成樹。
最小生成樹用於解決圖結構中的節點連通問題，怕一開始提到太多特殊名詞，讓我們直接按順序來吧。
樹與圖的差異主要體現在三點上
綜上所述，樹必定為一個無向連通無環圖，圖則不一定是樹。
那標題裡提到的生成樹又是什麼呢？
生成樹指的是在無向圖的結構裡的一顆子樹，必須符合下列條件：
這個最小指的是當今天的邊存在權重的時候，我們如何在眾多生成樹中，挑出一顆所有邊長權重加總後最小的生成樹。
那再來就要介紹我們的算法了。
一般解決最小生成樹的問題，我們有兩種演算法：Kruskal 和 Prim 算法。
算法的理念是我們會知道共有 n 個點和 m 個邊，將這 m 個邊依照邊的權重(低的優先)排序放入到一個佇列。
初始將所有點視作各自獨立，會挑選邊來讓點連通。
挑選的方式是，從權重最低的邊開始依序檢查，該邊所連接的兩個點是否已連通，若未連通，則這條邊會被挑選為最後用到的邊，並讓兩點連通，以此類推。
那什麼時候我們確認最小生成樹生成呢？當 n - 1 條邊被挑出來的時候，因為無環且連通的特性，最小生成樹的邊數必定為 n -1 條邊。
實作的時候，昨天介紹的併查集就派上用場了，確認兩個點是否連通，正好就是併查集的拿手好戲。而合併，也是併查集的基本功能，所以配合併查集，就能實作 Kruskal 算法讓我們得到最小生成樹。
這就是 Kruskal 的演算法邏輯，時間複雜度上，排序需要 log n 的時間，遍歷 m 個邊，併查集中的合併與查詢都會是近乎常數時間的花費，所以最後的時間複雜對會是 O(m log n)。
和 Kruskal 相對，Prim 不須一開始就對所有邊做排序，Prim 重視的是由點構成樹的過程。
Prim 把圖中的點分兩種，一種是以被選用的(標示為 u)，一種是尚未被選用的(標示為 v)。
被選用的點會放入一個集合中保存，我們稱作集合 U。
最開始，我們可以挑選任一個點做開始，選了點後，將該點放入集合 U。
從集合 U 裡的所有點，找到直接連結到尚未在集合 U 中，那些點 v 的所有路徑，從中挑選出權重最小的路徑，選擇該條路徑，把路徑連接的另一個點加入集合 U 中。
如此不斷重複，可以想見 U 中的點 u 數量會越來越多，點 v 的數量越來越少，直到所有的點都在集合 U 中，則最小生成樹建構完成。
在數據結構的選用上，我們可以用優先級佇列(Priority Queue)來實作邊的儲存，只須對邊的權重做一次排序與變於查詢，假設總共有 m 條邊在圖中，優先級佇立列的排序花費是 O(log m)，最壞的情況需要遍歷所有的邊 O(m)，所以時間複雜度為 O(m log m)。
講了這麼多，實作能幫我們建立實感。
這個方法處理的問題，白話的說，就是在圖中找一條能夠連接所有點且成本最低的路線。
只要是在無向連通圖中，則我們就能用這個方法來處理。
如情境可能像是所有的村莊本來都由泥巴路連接，今天要鋪水泥，要挑選那些村莊間的路來鋪，才能夠花最少成本，又讓所有村莊都被水泥路連接在一起呢？諸如此類的問題。
我們今天先用比較沒那麼生活化的例子來看一下(因為上面那個問題我在 Leetcode 上看是要訂閱的，如果你有訂閱想看，連結在這裡)，Min Cost to Connect All Points，其實題目的名稱也已經跟我們通篇描述已經對上了。
題目給予一個陣列，裡面包含 n 個點，假設點的座標為 point[i] = [xi,yi]，點與點之間的距離是兩個 x 相減後的絕對值加上兩個 y 相減後的絕對值(|xi-xj|+|yi-yj|)。題目要求我們回傳連接所有點的最小路徑成本。
算法原理在上面都講完了，下面讓我直接秀程式碼吧。
public class Solution {
public class UnionFind{
public int[] nodes;
public UnionFind(int n){
nodes = new int[n];
for(var i = 0; i < n; i++){
nodes[i] = i;
}
}
public int Find(int n){
if(nodes[n] == n){
return n;
}
else{
var root = Find(nodes[n]);
nodes[n] = root;
return root;
}
}
public bool IsSame(int n1, int n2){
return Find(n1) == Find(n2);
}
public void Union(int n1, int n2){
var n1Root = Find(n1);
var n2Root = Find(n2);
if(n1Root == n2Root){
return;
}
nodes[n2Root] = n1Root;
}
}
public class Edges{
public int node1;
public int node2;
public int distance;
public Edges(int node1, int node2, int[] node1Cood, int[] node2Cood){
this.node1 = node1;
this.node2 = node2;
this.distance = Math.Abs(node1Cood[0] - node2Cood[0]) + Math.Abs(node1Cood[1] - node2Cood[1]);
}
}
public int MinCostConnectPoints(int[][] points) {
var uf = new UnionFind(points.Length);
var edges = new List<Edges>();
for(var i = 0; i < points.Length; i++){
for(var j = i + 1; j < points.Length; j++){
edges.Add(new Edges(i, j, points[i], points[j]));
}
}
edges = edges.OrderBy(x=>x.distance).ToList();
var edgeChoosen = 0;
var cost = 0;
for(var i = 0; i < edges.Count; i++){
var isSame = uf.IsSame(edges[i].node1, edges[i].node2);
if(isSame){
continue;
}
uf.Union(edges[i].node1, edges[i].node2);
cost += edges[i].distance;
edgeChoosen++;
if(edgeChoosen == points.Length - 1){
break;
}
}
return cost;
}
}
public class Solution {
public void AddEdges(int[][] dist, PriorityQueue<int,int> pq, int node, bool[] visited){
for(var i = 0; i < dist[node].Length; i++){
if(visited[i]){
continue;
}
pq.Enqueue(i, dist[node][i]);
}
}
public int MinCostConnectPoints(int[][] points) {
var dist = new int[points.Length][];
for(var i = 0; i < points.Length; i++){
dist[i] = new int[points.Length];
for(var j = 0; j < points.Length; j++){
dist[i][j] = Math.Abs(points[i][0] - points[j][0]) + Math.Abs(points[i][1] - points[j][1]);
}
}
var visited = new bool[points.Length];
var cost = 0;
var choosenNode = 1;
var pq = new PriorityQueue<int,int>();
visited[0] = true;
AddEdges(dist, pq, 0, visited);
while(pq.TryDequeue(out int node, out int priority) && choosenNode < points.Length){
if(visited[node]){
continue;
}
visited[node] = true;
cost += priority;
AddEdges(dist, pq, node, visited);
choosenNode++;
}
return cost;
}
}
這題比較麻煩，因為不是直接給邊，要自己算一下權重，但核心算法確實就是如上所述。
建議一定要手動實做過，確認不是只懂概念，實作跟單純概念還是有些差距。
理解今天這兩種算法後，在無向連通圖裡，我們已經可以解決最小生成樹的問題了。
明天讓我們來看看，如果圖是「有向」，那我們該怎麼處理。
iThome鐵人賽
看影片追技術