写在前面

总结摘抄自labuladong

「树」和「图」的根本区别：树不会包含环，图可以包含环。一幅图可以有很多不同的生成树, 在所有可能的生成树中，权重和最小的那棵生成树就叫「最小生成树」。

  • Kruskal 算法：对所有的边进行权重排序，从小到大依次加入对应的边，同时利用并查集（Union-Find）算法保证加入这条边不会形成环，加入过程中维护权重和即可。
  • Prim 算法：从任意一个节点开始，不断加入与树中节点相关的横切边，为了保证每次加入的横切边里最小的，为了快速高效的找到最小横切边，使用优先队列（最小堆）来存储树中节点相关的横切边，同样使用visited数组避免成环（同时也可以避免加入相同的横切边）。 （BFS 算法思想）

Kruskal 算法是在一开始的时候就把所有的边排序，然后从权重最小的边开始挑选属于最小生成树的边，组建最小生成树。

Prim 算法是从一个起点的切分（一组横切边）开始执行类似 BFS 算法的逻辑，借助切分定理和优先级队列动态排序的特性，从这个起点「生长」出一棵最小生成树。

一些收获

  • 牢记优先队列的排序写法：

    // {point i, point j, weight}
auto cmp = [](const vector<int>& a, const vector<int>& b){return a[2] > b[2];};
priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> Q(cmp);

  • 特别是二维平面中的点：如果不是矩阵，则用题目中的点的索引来表示一个节点，如果用矩阵的方式给出，在可以用通过i*n+y或者i+y*m来线性化映射到一维空间。

Kruskal 算法框架

Union-Find算法+升序排列权重边+依次加入边构建树

// Union-Find算法
class UF {
    vector<int> parent;
public:
    // 构造函数
    UF(int n) {
        for(int i=0;i<n;i++) {
            parent.push_back(i);
        }
    }
    // 连接节点
    void union_(int x,int y) {
        int rootx=find(x);
        int rooty=find(y);
        if(rootx!=rooty){
            parent[rootx]=rooty;
        }
    }
    // 判断是否连接
    bool isconnected(int x,int y) {
    }
    // 查找根节点
    int find(int x) {
        if(x!=parent[x]) {
            parent[x]=find(parent[x]);
        }
        return parent[x];
    }
};
// 计算距离矩阵
vector<vector<int>> matrix;
// 具体实现-----
// 升序排列
sort(matrix.begin(),matrix.end(),[](vector<int>&a,vector<int>&b){
            return a[2]<b[2];
        });
// 构建树，过程中维护题目要求的权重信息

Prim 算法

BFS遍历思想+visited数组避免重复+优先队列容器（动态更新最小横切边）

1584. 连接所有点的最小费用

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        // 节点数目
        int pnums=points.size();
        // 计算距离矩阵: 无向图邻接表
        vector<vector<pair<int,int>>> matrix(pnums);
        for(int i=0;i<pnums-1;i++) {
            for(int j=i+1;j<pnums;j++) {
                // 两点之间的距离
                int x1= points[i][0]-points[j][0];
                int y1=points[i][1]-points[j][1];
                int xlim=x1>0 ? x1 : -x1;
                int ylim= y1>0 ? y1 : -y1;
                matrix[i].push_back(make_pair(j,xlim+ylim));
                matrix[j].push_back(make_pair(i,xlim+ylim));
            }
        }
        // 构建邻接表
        // 数据类型，容器，排序算法
        // {point i, point j, weight}
        auto cmp = [](const std::vector<int>& a, const std::vector<int>& b) { return a[2] > b[2]; };
    std::priority_queue<std::vector<int>, std::vector<std::vector<int>>, decltype(cmp)> Q(cmp);
        // 访问数组
        vector<bool> visited(pnums,false);
        visited[0]=true;
        // 从零开始
        for(auto s:matrix[0]) {
            Q.push({0,s.first,s.second});
        }
        int weight=0;
        int count=1;
        while(count<pnums) {
            vector<int> tt=Q.top();
            Q.pop();
            // 如果to已经在树中，则放弃
            int n1=tt[0],n2=tt[1],w=tt[2];
            if(visited[n2]) continue;
            visited[n2]=true;
            count++;
            weight+=w;   // 增加weight
            // 加入新的横切边
            for(auto s:matrix[n2]) {
                if(visited[s.first])
                    continue;
                Q.push({n2,s.first,s.second});
            }
        }
        return weight;
    }
};

$\cdots$ end $\cdots$