在Python中实现不相交集合系统 [英] Implementing Disjoint Set System In Python

问题描述

到目前为止，我所拥有的大部分是基于Cormen等人的算法导论的第571页。

我在Python中有一个Node类，代表set：

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ def $ _ $ __ _ _ .parent = parent
self.rank = rank

这个实现将使用一个列表的节点作为森林（我打开更好的方式来存储集）。

初始化）返回一个节点列表，我将把它存储在变量 set 中，并传递给其他函数。

Find 通过森林搜索该值并返回它出现的集合。我选择使用 （len（set））：这样在递归中，我可以缩小由 set [s：] 传入的集合列表。

  def查找（set，value）：
在范围内（len（set））：
如果value！= set [s ] .parent：
 set [s] .parent = Find（set [s：]，set [s] .parent）
 return set [s] 

$ p $合并通过查找它们并提升排名较高的集合来合并森林中的集合。

  def合并（set，value1，value2）：
 set_val_1 =查找（set，value1）
 set_val_2 =查找（set，value2） 
如果set_val_1.rank> set_val_2.rank：
 set_val_2.parent = set_val_1 
 else：
 set_val_1.parent = set_val_2 
如果set_val_1.rank == set_val_2.rank ：
 set_val_2.rank + = 1 

c $ c>查找 s和合并 s，即查找没有返回正确设置，所以我不知道如果合并也正常工作。我很感激一些帮助，以确保功能正常实施。

解决方案

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

我认为你的错误是认为森林必须存储在一个集合中，而你必须遍历这个集合来完成节点上的操作。从 Merge（）和 Find（）中删除​​ set 执行 Find（）作为

  def Find（n）：
如果n！= n.parent：
 n.parent = Find（n.parent）
 return n.parent 
  

就像书中一样。然后添加一个 MakeSet（），它返回一个正确初始化的节点，也许还有一个 SameSet（）函数： / p>



  def SameSet（n1，n2）：
 return Find（n1）== Find（n2）
  

您现在有一个不相交的集合实现。

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

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

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

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

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 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

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.

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

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.

这篇关于在Python中实现不相交集合系统的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！