数据结构编程实践20讲(Python版)—20并查集

往期链接

20 并查集（Union-Find Set）

S1 说明

并查集的定义

并查集，又称为不相交集合数据结构，是一种用于处理 合并和查询 操作的数据结构。

并查集基本操作

• 查找Find：查找元素 x 所在集合的代表元（根节点）。通过代表元，可以确定两个元素是否属于同一个集合。
• 合并Union：将两个元素所在的集合合并。通常将一个集合的根节点连接到另一个集合的根节点上。

并查集优化

• 路径压缩优化（Path Compression）：在执行 Find 操作时，将查找路径上的所有节点直接连接到根节点。这样可以有效地降低树的高度，加快后续操作。
• 按秩合并优化（Union by Rank）：在 Union 操作时，将树高度（秩）较小的根节点连接到树高度较大的根节点上，避免树高度增加。

同时使用路径压缩和按秩合并，可以使得并查集的操作时间复杂度近似为 $O(\alpha (n))$，其中 $\alpha (n)$ 为阿克曼函数的逆，增长极其缓慢，近似为常数时间。

并查集特点

• 高效性：在经过路径压缩和按秩合并的优化后，并查集的 Find 和 Union 操作的平均时间复杂度近似为常数。
• 适用性：适用于需要动态维护元素分组的信息，特别是判断两个元素是否在同一集合的场景。
• 易于实现：并查集的基本实现相对简单，可以根据需要进行优化。

应用领域

• 动态连通性问题

在一个网络中，动态地添加连接，判断两个节点是否连通。

• 最小生成树算法

在 Kruskal 算法中，使用并查集判断添加的边是否会形成环，以决定是否将边加入生成树。

• 等价类划分

将一些具有特定关系的元素分组，例如在语言处理中的同义词分组。

• 网络社交圈检测

在社交网络中，判断用户之间是否在同一个社交圈中。

• 图的连通分量

在无向图中，使用并查集可以快速找到连通分量的个数。

S2 示例

class UnionFind:
    def __init__(self, elements):
        """初始化并查集。

        参数：
        elements -- 一个包含所有元素的可迭代对象
        """
        self.parent = {}  # 记录每个节点的父节点
        self.rank = {}    # 记录每个节点的秩（近似树的高度）
        for element in elements:
            self.parent[element] = element
            self.rank[element] = 0

    def find(self, x):
        """查找元素 x 所在集合的根节点，并进行路径压缩。"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 递归查找，并路径压缩
        return self.parent[x]

    def union(self, x, y):
        """合并元素 x 和 y 所在的集合，按秩合并。"""
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return  # 已经在同一集合中，无需合并

        # 按秩合并
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        elif self.rank[xroot] > self.rank[yroot]:
            self.parent[yroot] = xroot
        else:
            self.parent[yroot] = xroot
            self.rank[xroot] += 1

if __name__ == "__main__":
    # 初始化并查集
    elements = [1, 2, 3, 4, 5]
    uf = UnionFind(elements)

    # 合并操作
    uf.union(1, 2)
    print(f"1 和 2 是否连通: {uf.find(1) == uf.find(2)}")  # 输出 True

    uf.union(2, 3)
    print(f"1 和 3 是否连通: {uf.find(1) == uf.find(3)}")  # 输出 True

    uf.union(4, 5)
    print(f"3 和 5 是否连通: {uf.find(3) == uf.find(5)}")  # 输出 False

    uf.union(3, 5)
    print(f"1 和 5 是否连通: {uf.find(1) == uf.find(5)}")  # 输出 True

结果

1 和 2 是否连通: True
1 和 3 是否连通: True
3 和 5 是否连通: False
1 和 5 是否连通: True

S3 问题1：朋友圈问题

问题描述：在一个班级里，有$n$个学生，编号为$0$到$n-1$。每个学生可能认识其他一些学生，形成了好友关系。好友关系是互相的，也就是说，如果学生$A$是学生$B$的好友，那么学生 $B$也是学生$A$的好友。

给定一个$n\times n$的二维矩阵$M$，其中

• $M[i][j]=1$ 表示第$i$个学生和第$j$个学生是直接的好友关系。
• $M[i][j]=0$ 表示第$i$个学生和第$j$个学生不是直接好友。

朋友圈：一组学生，他们之间是直接或间接的好友关系。也就是说，如果学生$A$和学生$B$是直接好友，或者通过其他学生间接相连（比如$A$是$C$的好友，$C$是$B$的好友），那么$A$和 $B$属于同一个朋友圈。

请计算班级中共有多少个不同的朋友圈（Friend Circles）。

class UnionFind:
    def __init__(self, n):
        """初始化并查集"""
        self.parent = [i for i in range(n)]  # 父节点
        self.rank = [0] * n                  # 秩
        self.count = n                       # 集合数量，可直接作为朋友圈数量

    def find(self, x):
        """查找根节点（带路径压缩）"""
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径压缩：父节点指向祖父节点
            x = self.parent[x]
        return x

    def union(self, x, y):
        """合并两个节点所在的集合"""
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return
        # 按秩合并
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        else:
            self.parent[yroot] = xroot
            if self.rank[xroot] == self.rank[yroot]:
                self.rank[xroot] += 1
        self.count -= 1

def findCircleNum(M):
    n = len(M)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i+1, n):  # 只遍历上三角矩阵，减少重复
            if M[i][j]:
                uf.union(i, j)
    return uf.count

# 测试代码
if __name__ == "__main__":
    M = [
        [1,1,0,0,0,0,0,0,0,0],
        [1,1,1,0,0,0,0,0,0,0],
        [0,1,1,0,0,0,0,1,0,0],
        [0,0,0,1,1,0,0,0,0,0],
        [0,0,0,1,1,0,0,0,0,0],
        [0,0,0,0,0,1,0,0,0,0],
        [0,0,0,0,0,0,1,1,0,0],
        [0,0,1,0,0,0,1,1,0,0],
        [0,0,0,0,0,0,0,0,1,1],
        [0,0,0,0,0,0,0,0,1,1],
    ]
    print("朋友圈数量：", findCircleNum(M))  # 输出：4

例子说明

M = [
    [1,1,0,0,0,0,0,0,0,0],  # 学生0与学生1是好友
    [1,1,1,0,0,0,0,0,0,0],  # 学生1与学生2是好友
    [0,1,1,0,0,0,0,1,0,0],  # 学生2与学生7是好友
    [0,0,0,1,1,0,0,0,0,0],  # 学生3与学生4是好友
    [0,0,0,1,1,0,0,0,0,0],  # 学生4与学生3是好友
    [0,0,0,0,0,1,0,0,0,0],  # 学生5自己一个朋友圈
    [0,0,0,0,0,0,1,1,0,0],  # 学生6与学生7是好友
    [0,0,1,0,0,0,1,1,0,0],  # 学生7与学生2和6是好友
    [0,0,0,0,0,0,0,0,1,1],  # 学生8与学生9是好友
    [0,0,0,0,0,0,0,0,1,1],  # 学生9与学生8是好友
]

朋友圈1：学生0、1、2、7、6组成一个朋友圈，因为他们通过直接或间接的好友关系连接在一起。
朋友圈2：学生3和学生4组成一个朋友圈。
朋友圈3：学生5自己一个人，是一个朋友圈。
朋友圈4：学生8和学生9组成一个朋友圈。

S4 问题2：网络连接恢复问题

在一个网络中，有$n$个节点，这些节点通过若干边相连。然而，由于某些原因，部分连接（边）被破坏，导致网络分裂成多个连通的子网络。为了恢复整个网络的连接性，我们需要添加最少数量的边，使得所有节点重新连通。目标是最小化需要添加的边的数量，使得网络变为连通图。

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]  # 节点编号从 1 到 n
        self.rank = [0] * (n + 1)

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径压缩
            x = self.parent[x]
        return x

    def union(self, x, y):
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return False  # 已在同一集合
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        else:
            self.parent[yroot] = xroot
            if self.rank[xroot] == self.rank[yroot]:
                self.rank[xroot] += 1
        return True


def get_additional_edges(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    # 收集连通分量的根节点
    connected_components = set()
    for i in range(1, n + 1):
        parent = uf.find(i)
        connected_components.add(parent)
    components = list(connected_components)
    # 构造需要添加的边的列表
    additional_edges = []
    for i in range(len(components) - 1):
        u = components[0]
        v = components[i + 1]
        additional_edges.append([u, v])
    return additional_edges


# 测试代码
if __name__ == "__main__":
    n = 8
    edges = [[1, 2], [2, 3], [4, 5], [2, 7]]
    additional_edges = get_additional_edges(n, edges)
    print("需要添加的边：", additional_edges)  

需要添加的边： [[8, 1], [8, 4], [8, 6]]

S5 问题3：随机生成迷宫

import random
import matplotlib.pyplot as plt

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]  # 父节点数组
        self.rank = [0] * size  # 秩数组，用于按秩合并

    def find(self, x):
        # 路径压缩查找
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 递归压缩路径
        return self.parent[x]

    def union(self, x, y):
        # 按秩合并
        xroot = self.find(x)
        yroot = self.find(y)
        if xroot == yroot:
            return False  # 已在同一集合，不能合并
        if self.rank[xroot] < self.rank[yroot]:
            self.parent[xroot] = yroot
        else:
            self.parent[yroot] = xroot
            if self.rank[xroot] == self.rank[yroot]:
                self.rank[xroot] += 1
        return True  # 合并成功

class Maze:
    def __init__(self, rows, cols):
        self.rows = rows
        self.cols = cols
        # 每个格子存储其墙壁状态，N、S、E、W 分别表示北、南、东、西
        self.maze = [[{'walls': {'N': True, 'S': True, 'E': True, 'W': True}} for c in range(cols)] for r in range(rows)]
        self.walls = []

    def init_walls(self):
        # 初始化所有的墙壁
        for r in range(self.rows):
            for c in range(self.cols):
                cell_index = r * self.cols + c
                # 东边墙壁
                if c < self.cols - 1:
                    self.walls.append((cell_index, cell_index + 1, 'E'))
                # 南边墙壁
                if r < self.rows - 1:
                    self.walls.append((cell_index, cell_index + self.cols, 'S'))

    def remove_wall(self, cell1, cell2, direction):
        r1, c1 = divmod(cell1, self.cols)
        r2, c2 = divmod(cell2, self.cols)
        # 移除墙壁
        if direction == 'E':
            self.maze[r1][c1]['walls']['E'] = False
            self.maze[r2][c2]['walls']['W'] = False
        elif direction == 'S':
            self.maze[r1][c1]['walls']['S'] = False
            self.maze[r2][c2]['walls']['N'] = False

def generate_maze(rows, cols):
    maze = Maze(rows, cols)
    maze.init_walls()

    uf = UnionFind(rows * cols)
    # 随机排列墙壁列表
    random.shuffle(maze.walls)

    for wall in maze.walls:
        cell1, cell2, direction = wall
        # 判断两个格子是否属于不同的集合
        if uf.union(cell1, cell2):
            # 如果合并成功，移除墙壁
            maze.remove_wall(cell1, cell2, direction)
        # 如果合并失败，说明已连通，不能移除墙壁，以避免形成环

    return maze

def add_entry_exit(maze):
    # 移除左上角的西边墙壁作为入口
    maze.maze[0][0]['walls']['W'] = False
    # 移除右下角的东边墙壁作为出口
    maze.maze[maze.rows - 1][maze.cols - 1]['walls']['E'] = False

def draw_maze(maze):
    rows = maze.rows
    cols = maze.cols
    maze_map = maze.maze

    # 设置绘图尺寸
    plt.figure(figsize=(cols / 2, rows / 2))
    ax = plt.gca()
    ax.set_aspect('equal')
    plt.axis('off')  # 关闭坐标轴

    # 绘制迷宫
    for r in range(rows):
        for c in range(cols):
            x = c
            y = rows - r - 1  # Matplotlib 的 y 轴方向与迷宫的行数相反

            walls = maze_map[r][c]['walls']

            # 设置墙壁的线宽
            line_width = 2

            # 如果北边有墙壁，绘制从 (x, y+1) 到 (x+1, y+1) 的线
            if walls['N']:
                plt.plot([x, x + 1], [y + 1, y + 1], color='black', linewidth=line_width)
            # 如果南边有墙壁，绘制从 (x, y) 到 (x+1, y) 的线
            if walls['S']:
                plt.plot([x, x + 1], [y, y], color='black', linewidth=line_width)
            # 如果西边有墙壁，绘制从 (x, y) 到 (x, y+1) 的线
            if walls['W']:
                plt.plot([x, x], [y, y + 1], color='black', linewidth=line_width)
            # 如果东边有墙壁，绘制从 (x+1, y) 到 (x+1, y+1) 的线
            if walls['E']:
                plt.plot([x + 1, x + 1], [y, y + 1], color='black', linewidth=line_width)

    plt.tight_layout()
    plt.show()

if __name__ == "__main__":
    rows = 20  # 迷宫的行数
    cols = 20  # 迷宫的列数
    maze = generate_maze(rows, cols)
    add_entry_exit(maze)  # 添加入口和出口
    draw_maze(maze)  # 使用 Matplotlib 可视化迷宫