最小生成树（并查集 & Kruskal & Prim）

概念

树：$n$个点，$n-1$条边の连通图。

生成树：连通图的生成树是包含图中全部顶点的一个极小连通子图。

最小生成树：所有生成树中边权和最小的。

并查集

用于解决连通性问题。

并（合并 $Union$）查（查询 $Find$）集

struct DSU {
    vector<int> parent; // 存储每个节点的父节点
    vector<int> size;   // 存储每个集合的大小

    //初始化并查集
    DSU(int n) {
        // 调整数组大小为n
        parent.resize(n);
        size.resize(n);
        
        // 初始化每个节点的父节点为自身，集合大小为1
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 查找x所在集合的根节点（路径压缩）
    int find(int x) {
        // 如果x不是根节点，将其父节点设为根节点
        if (parent[x] != x) 
            parent[x] = find(parent[x]);
        
        return parent[x];
    }

    // 合并x和y所在的集合
    void unite(int x, int y) {
        // 找到两个节点的根节点
        x = find(x);
        y = find(y);
        
        // 如果已经在同一集合，直接返回
        if (x == y) return;
        
        // 按集合大小合并（启发式合并）
        if (size[x] < size[y]) {
            parent[x] = y;      // 小集合合并到大集合
            size[y] += size[x]; // 更新大集合的大小
        } else {
            parent[y] = x;
            size[x] += size[y];
        }
    }
};

Kruskal算法

算法过程

复杂度$O(mlogm)$

1 初始化。

​ 将所有边从小->大排序 && 将并查集初始化。

2 按排序后の顺序，选择权值最小の边$(u,v,w)$。

3 若节点$u\in A,v\in B$（两个节点属于不同的集合），

​ 则，将$(u,v)$加入边集 && 合并两个集合。

4 若选取边数小于$n-1$，

​ 则，-> 2；

​ 否则，结束。

代码模板

伪代码（摘自OI-wiki）

const int N = 5e5 + 10; 

// 并查集
struct DSU{
     int fa[N];  // 存储每个节点的父节点

     // 初始化并查集，将每个节点的父节点设为自身
     void init(int n) {
          for (int i = 1; i <= n; i ++)
               fa[i] = i;
     }

     // 查找节点x的根节点 && 路径压缩：递归查找时，将节点的父节点直接设为根节点
     int find(int x) {
          if (fa[x] == x)  // 当前节点是根节点，直接返回
               return x;
          return fa[x] = find(fa[x]);  // 递归查找并压缩路径
     }

     // 合并节点x和y所在的集合
     void uni(int x, int y) {
          x = find(x), y = find(y);  // 先找到两个节点的根节点
          fa[x] = y;  // 将x的根节点的父节点设为y的根节点
     }
}dsu;

// 用于存储图的边信息
struct edge{
     int u, v, w;

     // 重载小于运算符，用于边的排序
     // 按边的权重升序排列
     bool operator< (const edge& you)const{return w < you.w;}
}e[N]; 

Prim算法

算法过程

从一个点开始拓展 -> 求出整个MST

1 从某点开始，遍历该点可访问の边，标记它们为可用。

2 在所有可用の边中寻找最小边，该边必有一点 u 未访问过，则将 u 与该边都加入MST。

3 用 u 更新MST。

​ 若到 u 的距离更短，则更新为可用，并把原边更新为不可用。

4 重复 2 ~ 4，直至没有新の点。

此时，所有边构成の树即为MST。

代码模板

伪代码（摘自OI-wiki）

int main () {
    // 初始化距离数组f为无穷大
    memset(f, 0x3f, sizeof f);
    // 初始化访问标记数组vis为false，表示所有节点均未被访问
    memset(vis, false, sizeof vis);

    // 起点到自身的距离为0
    f[1] = 0;
    vis[1] = true;

    int last = 1;

    // 初始化距离数组：将节点1到其他所有节点的直接距离存入f
    // g是存储图的邻接矩阵，g[1][i]表示节点1到节点i的边权
    for (int i = 1; i <= n; i ++)
        f[i] = g[1][i];
    // 将邻接矩阵中“自身到自身”的距离设为无穷大（避免自环）
    for (int i = 1; i <= n; i ++)
        g[i][i] = inf;
   
    // Prim算法：构建最小生成树需要n-1条边
    for (int i = 1; i < n; i ++) {
        // 记录当前未访问节点中，到已选集合的最小距离（设为无穷大）
        int minw = inf;
        // 记录距离最小的节点编号（设为-1表示未找到）
        int minj = -1;

        // 遍历所有节点，找到未访问且距离已选集合最近的节点
        for (int j = 1; j <= n; j ++) {
            // 如果节点j未被访问，且当前距离小于记录的最小距离
            if (! vis[j] && f[j] < minw) {
                // 更新最小距离节点和对应的距离值
                minj = j;
                minw = f[j];
            }
        }

        // 如果没有找到可连接的节点（图不连通），退出循环
        if (minj == -1)
            break;
        
        // 累计最小生成树的总权值
        ans += minw;
        // 更新上一个选中的节点为当前找到的节点
        last = minj;
        // 标记当前节点已被访问（加入已选集合）
        vis[minj] = 1;

        // 松弛操作
        for (int j = 1; j <= n; j ++) {
            // 如果从新节点minj到节点j的距离，比当前记录的距离更短，则更新
            if (g[minj][j] < f[j]) 
                f[j] = g[minj][j];
        }
    }
}

END

尾图

24年の天依游学记