Cloud_Player's Notes
0%

并查集与最小生成树

发表于 更新于
本文字数： 5.1k 阅读时长 ≈ 5 分钟

b站视频链接：北京理工大学ACM冬季培训课程
课程刷题地址 2020BIT冬训-并查集&最小生成树 但是没得密码。。。
本篇博文为看视频学习时的记录与自己的一些总结

并查集&最小生成树

并查集

问题提出

假设有 n 个强盗，其中可能有很多帮派，给出关系链（某人和某人是同伙）。然后给出多个查询，询问其中两个人是不是一个帮派

问题解决方法

图染色

将连接两个端点及其所在块涂成一个颜色。合并时复杂度较高，查询时为 $O(1)$ 。

并查集

将某个强盗作为这个团队的代表人物（头目）。在修改时，使原本两个团队的代表人物（头目）具有从属关系（a，b 两个集合合并后，若 b 原来的头目是 a 的头目的下属，那么实际上 b 合并后的最高头目还是 a 的头目，通过修改头目的从属关系合并集合）。对于查询，只需查询是否两个集合的代表元素是同一个。在修改较多时，均摊复杂度优于图染色。

并查集

概念

并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
基础的并查集能实现以下三个操作：

  1. 建立集合
  2. 查找某个元素是否在一给定集合内（或查找一个元素所在的集合）
  3. 合并两个集合

“并”“查”“集”三字由此而来。

并查集能解决的问题一般可以转化成这样的形式：初始时 n 个元素分属不同的 n 个集合，通过不断的给出元素间的联系，要求 实时 的 统计元素间的关系 （即是否存在直接或间接的联系）。

并查集本身不具有结构，可以用数组、链表以及树等实现。最常用的是 数组 实现

实现

数组实现：
建立标记数组 father，用 father[i] 表示元素 i 所属集合（头目）的标记。

1. 建立集合，初始化
1
2
3
4
5
void init()
{
    for(int i = 1; i <= n; i++)
        father[i] = i;
}
2. 合并集合&查找集合所属元素

查找就是寻找头目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int find(int x)//非递归写法
{
    while(father[x]!=x)
        x=father[x];
    return x;
}

int find(int x)//递归写法
{
    if(father[x]!=x)
        return find(father[x]);
    else
        return x;
}

因此，比较两个元素 x,y 是否是同一集合的方法就是比较 find(x) 是否等于 find(y)。

1
2
3
4
5
6
7
8
9
bool judge(int x, int y)
{
    x = find(x);
    y = find(y);
    if(x == y)
        return true;
    else
        return false;
}

合并集合的方法就是将其中一个点所在集合的根结点的父结点设定为另一个点所在集合的根结点。

1
2
3
4
5
6
void union1(int x, int y)//union是关键字，不能用，函数名可以随便换一个方便的
{
    x = find(x);
    y = find(y);
    father[y] = x;
}

优化

路径压缩

路径压缩就是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲结点都设为根结点

路径压缩前示意图

路径压缩后示意图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int find(int x)//递归写法
{
    if(father[x]!=x)
        father[x]=find(father[x]);
    return father[x];
}
int find(int x)//非递归写法，不太好记但是更快，列几组数据试一下也不难理解
{
    int r=x,q;
    while(r!=father[r])
        r=father[r];
    while(x!=r)
    {
        q=father[x];
        father[x]=r;
        x=q;
    }
    return r;
}

（这个优化平时都可以用，但是对于某些题会造成麻烦，例如加权并查集，这样的题需要特殊处理）

按秩合并（启发式合并）

在合并两个集合（就是两棵树）的时候，如果待合并的树的深度不相同，那么就有两种选择：

  1. 一种是以深度较小的树的根结点为新的根结点
  2. 另一种是以深度较大的树的根结点为新的根结点

而事实上，选择以深度较大的树的根节点为新的根节点较好，因为这样的话新生成的树深度会更小，可以防止树的退化（退化指越来越接近链表，即深度大而分支少），使资源利用更合理。而合并时这样选择，就叫作“按秩合并”

按秩合并的基本思想是将深度较小的树指到深度较大的树的根上

按秩合并需要新开一个数组depth来记录深度，depth[x]是("以 x 为根结点的树"的某个叶结点到 x 的最长路径上)边的数目的一个最大值。（即以 x 为根结点的树的树高）

（这个优化比较麻烦，简单题一般不用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void init()
{
    int i
    for(i = 1; i <= n; i++)
    {
        father[i] = i;
        depth[i] = 0; // 如果初值为 0 则可以忽略
    }
}

void union1(int x, int y)
{
    int fx = find(x), fy = find(y);
    if(depth[fx] > depth[fy])
        father[fy] = fx;
    else
    {
        father[fx] = fy;
        if(depth[fx] == depth[fy])
            depth[fy]++;
    }
}

应用

  • kruskal

变种

加权并查集

最小生成树

Prim 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void MiniSpanTree_PRIM(MGraph G, VertexType u) {
    // 用 Prim 算法从第 u 个顶点出发构造网 G 的最小生成树 T，输出 T 的各条边
    // 记录从顶点集 U 到 V-U 的代价最小的边的辅助数组定义
    // struct {
    //     VertexType adjvex;
    //     VRType lowcost;
    // }closedge[MAX_VERTEX_NUM];
    k = LocateVex(G, u);
    for (j = 0; j < G.vexnum; ++j)       // 辅助数组初始化
        if (j! = k) closedge[j] = { u, G.arcs[k][j].adj };    // {adjvex, lowcost}
    closedge[k].lowcost = 0;             // 初始，U = {u}
    for (i = 1; i < G.vexnum; ++i) {     // 选择其余 G.vexnum - 1 个顶点
        k = mininum(closedge);           // 求出 T 的下一个结点：第 k 顶点
        // 此时 closedge[k].lowcost =
        //              MIN{ closedge[Vi].lowcost | closedge[Vi].lowcost > 0, Vi ∈ V-U }
        printf(closedge[k].adjvex, G.vexs[k]);      // 输出生成树的边
        closedge[k].lowcost = 0;                    // 第 k 顶点并入 U 集
        for (j = 0; j < G.vexnum; ++j)
            if (G.arcs[k][j].adj < closedge[j].lowcost) // 新顶点并入 U 后重新选择最小边
                closedge[j] = { G.vexs[k], G.arc[k][j].adj };
    }
} // MiniSpanTree

Prim 算法的 C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void prim(int u){                       // 传入起点
    int sum_mst = 0;                    // 总权值初始化
    for(int i = 1; i <= n; i++){        // 初始化 lowcost mst 辅助数组
                                        // lowcost[i] 表示以 i 为终点的边的最小权值
                                        // mst[i] 表示对应 lowcost[i] 的起点且 mst[i] = -1 表示起点 i 加入 MST
        lowcost[i] = Map[u][i];         // 数组存图：Map[起点][终点] = 权值
        mst[i] = u;                     // 默认 mst 数组的初始值为 u
    }
    mst[u] = -1;                        // 起点加入 MST(Minimum Spanning Tree)
    for(int i = 1; i < n; i++){         // 迭代 n-1 次
        int minn = INF;                 // INF = 0x3f3f3f3f
        int v = -1;
        for(int j = 1; j <= n; j++){
            if(mst[j] != -1 && lowcost[j] < minn)
                                        // 不在 mst 数组中且其权值小于最小权值
            {
                v = j;
                minn = lowcost[j];
            }
        }
        if(v != -1)                     // 能找到下一结点
        {
            // 此处可输出路径
            mst[v] = -1;                // 下一结点加入 MST
            sum_mst += lowcost[v]       // 更新总权值
            for(int j = 1; j <= n; j++) // 更新 lowcost mst 数组
            {
                if(mst[j] != -1 && lowcost[j] > Map[v][j])
                                        // j 结点不在 MST 中且目前以 j 为终点的边的权值大于以 v 为起点、j 为终点的边的权值
                {
                    lowcost[j] = Map[v][j];
                    mst[j] = v;
                }
            }
        }
    }       // 此处可输出总权值
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 最小生成树 Prim
int edges[MAXN][MAXN];
int dist[MAXN];
bool vis[MAXN];
void add_edge(int from, int to, int value)
{
    edges[from][to] = max(edges[from][to], value);
    edges[to][from] = max(edges[to][from], value);
}
void init()
{
    memset(edges, -1, sizeof(edges));
    memset(dist, -1, sizeof(dist));
    memset(vis, false, sizeof(vis));
}
int prim(int n)
{
    vis[1] = true;
    for (int i = 2; i <= n; i++)
        dist[i] = edges[1][i];
    int ret = 0;
    for (int i = 2; i <= n; i++)
    {
        int x = 1;
        for (int j = 1; j <= n; j++)
            if (!vis[j] && dist[j] > dist[x]) x = j;
        ret += dist[x];
        vis[x] = true;
        for (int j = 1; j <= n; j++)
            if (!vis[j]) dist[j] = min(dist[j], edges[x][j]); 
    }
    return ret;
}

Kruskal 算法

Kruskal 算法的 C++ 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 最小生成树 Kruskal
struct Edge
{
    int from, to, value;
    // from 和 to 是两端点，value 是边权
    bool operator < (const Edge& rhs) const
    {// 按边权重载小于号，用于排序
        return value < rhs.value;
    }
};
int Kruskal(Edge* edges, int m)
{// edges 是边集，m 是边集大小
    sort(edges, edges + n);
    int ret = 0; // 生成权
    for (int i = 0; i < m; i++) {
        if (find(edges[i].from) == find(edges[i].to))
            continue; // 已经在同一连通块中
        ret += edges[i].value; // 将边权加入生成权
        merge(edges[i].from, edges[i].to); // 合并连通块
    }
    return ret;
}