最小生成樹Prim和Kruskal算法

生成樹是對圖周遊通路的一條無回路的周遊路徑稱為圖的生成樹，最小生成樹是對帶有權值的圖,生成樹路徑中權值總和最小的路徑,稱為最小生成樹.

以leetcode 5513. 連接配接所有點的最小費用為例

給你一個points 數組，表示 2D 平面上的一些點，其中 points[i] = [xi, yi] 。

連接配接點 [xi, yi] 和點 [xj, yj] 的費用為它們之間的 曼哈頓距離 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的絕對值。

請你傳回将所有點連接配接的最小總費用。隻有任意兩點之間 有且僅有 一條簡單路徑時，才認為所有點都已連接配接。

示例：

輸入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]

輸出：20

解釋：

我們可以按照上圖所示連接配接所有點得到最小總費用，總費用為 20 。

注意到任意兩個點之間隻有唯一一條路徑互相到達。

此題是模闆題，直接使用Prim算法或Kruskal算法即可求解；

Prim算法：

class Solution {
    int[] pre;
    public int minCostConnectPoints(int[][] points) {
        int ans=0;
        if(points.length==1) return ans;
        PriorityQueue<int[]> pq=new PriorityQueue<int[]>((e1,e2)->{
                return e1[1] - e2[1];
        });
        Set<Integer> vis=new HashSet<Integer>();
        pq.add(new int[2]);
        while(vis.size()<points.length){
            int[] head=pq.poll();
            if(!vis.contains(head[0])){
                vis.add(head[0]);
                ans+=head[1];
                for(int i=0;i<points.length;++i){
                    if(!vis.contains(i)){
                        pq.add(new int[]{i,Math.abs(points[i][0]-points[head[0]][0])+Math.abs(points[i][1]-points[head[0]][1])});
                    }
                }
            }
        }
        return ans;
    }
}
           

Prim算法一般複雜度為O(N^2)，基于點處理，直接可以通過vis标記是否通路排除回路，在對邊排序時可以使用優先隊列進行堆優化O(mlogn)，另外在内層for循環中，可以用鄰接表進行存儲。因為是基于點處理，是以适用于邊稠密的圖，此題是全連接配接的圖是以屬于邊密集型。

Kruskal（大佬）代碼：

#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define f first
#define s second
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
// END NO SAD
// REMEMBER CLEAR GLOBAL STATE
// REMEMBER READ THE PROBLEM STATEMENT AND DON'T SOLVE A DIFFERENT PROBLEM
// remember hidden T factor of 1e2
// read the bounds for stupid cases
// did you restart your editor
int par[1005];
int find(int x) {
  return par[x] == x ? x : (par[x] = find(par[x]));
}
bool merge(int x, int y) {
  x = find(x);
  y = find(y);
  if(x == y) return false;
  par[x] = y;
  return true;
}
class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int ret = 0;
        int n = sz(points);
        int need = n-1;
        vector<pair<int, pii>> edges;
        for(int i = 0; i < n; i++) par[i] = i;
        for(int i = 0; i < n; i++) for(int j = 0; j < i; j++) edges.emplace_back(abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), pii(i, j));
        sort(all(edges));
        for(auto& out: edges) {
          if(merge(out.s.f, out.s.s)) {
            ret += out.f;
            if(--need == 0) break;
          }
        }
        return ret;
    }
};
           

Kruskal算法是基于邊選取，但在判斷回路時較麻煩，需要用并查集進行回路判斷。基于邊處理，适用于邊稀疏的圖。