在 Python 中实现不相交集系统

2022-01-20 00:00:00 python merge find disjoint-sets

问题描述

到目前为止，我所掌握的内容主要基于 Cormen 等人的算法简介"第 571 页.

What I have so far is largely based off page 571 of "Introduction To Algorithms" by Cormen et al.

我在 python 中有一个 Node 类，它代表一个集合:

I have a Node class in python that represents a set:

class Node:
    def __init__(self, parent, rank = 0):
        self.parent = parent
        self.rank = rank

此实现将使用节点的 List 作为森林(我愿意接受更好的方法来存储集合).

This implementation is going to use a List of Nodes as the forest (I am open to better ways to store the sets).

Initialize() 返回一个节点列表，我将其存储在变量 set 中并传递给其他函数.

Initialize() returns a list of Nodes, that I will store in variable set and pass into the other functions.

Find 在森林中搜索值并返回它出现的集合.我选择使用 for s in range(len(set)): 所以在递归中，我可以缩小 set[s:] 传入的集合列表.

Find searches through the forest for the value and returns the set that it appears in. I chose to use for s in range(len(set)): so that in the recursion I could shrink the list of sets being passed in by set[s:]. 

def Find(set, value):
    for s in range(len(set)):
        if value != set[s].parent:
            set[s].parent = Find(set[s:], set[s].parent)
        return set[s]

Merge 通过找到它们并提升排名较高的集合来合并森林中的集合.

Merge merges sets in the forest by finding them and promoting the higher ranked set. 

def Merge(set, value1, value2):
    set_val_1 = Find(set, value1)
    set_val_2 = Find(set, value2)
    if set_val_1.rank > set_val_2.rank:
        set_val_2.parent = set_val_1
    else:
        set_val_1.parent = set_val_2
        if set_val_1.rank == set_val_2.rank:
            set_val_2.rank += 1

我在执行 Finds 和 Merges 时遇到了一些错误，即 Find 没有返回正确的集合，所以我我不确定 Merge 是否也能正常工作.我会很感激一些帮助，以确保正确实现这些功能.

I am getting some errors when I do Finds and Merges, namely Find is not returning the proper set, and so I am not sure if Merge is working properly as well. I would appreciate some help to make sure the functions are implemented properly.

解决方案

我没有这本书的最新版本，但这看起来不像是不相交的森林.

I don't have the latest edition of the book, but this doesn't look quite like a disjoint-set forest.

我认为您的错误是认为必须将森林存储在集合中，并且您必须遍历该集合才能对节点进行操作.从 Merge() 和 Find() 中移除 set 并实现 Find() as

I think your mistake is to think that the forest has to be stored in a collection and that you have to traverse this collection to do the operations on the nodes. Remove set from Merge() and Find() and implement Find() as

def Find(n):
    if n != n.parent:
        n.parent = Find(n.parent)
    return n.parent

就像书中一样.然后添加一个返回单个正确初始化节点的 MakeSet()，也许还有一个 SameSet() 函数:

just like in the book. Then add a MakeSet() that returns a single correctly initialized node, and maybe a SameSet() function too:

def SameSet(n1, n2):
    return Find(n1) == Find(n2)

你现在有一个工作的不相交集实现.

You now have a working disjoint set implementation.

相关文章