Java 路径压缩

Question

我必须创建一个 find 方法，该方法将使用本地 Set 来收集对象和根。然后，我将压缩对象 e(在参数中)并将栖息地作为其父对象。然后，我将返回对根的引用。我可以使用 Graph、Map 和 set 类，因为它是导入的。但是，我如何调用根的父级呢？我可以把mapParent.get(e)？

编辑该方法的作用是让节点指向根，我想用一个Set将参数和对象根之间的所有对象放在一起。然后，我会使用路径压缩。然后，我必须返回对该对象的引用。所以，我想知道如何调用对象的父对象以某种方式引用父对象。这就是我得到的:

public T find (T obj){
    //Set<E> s = new HashSet<E>(sizeOfRoot.size()); // i don't know how I would use the set yet
      T p = null;
      if (map.get(obj).equals(obj)) // I was trying to get the parent of e
          return obj; 
      else{
          p = find(map.get(obj)); // recursively call the method to path compress
      }

    return p; // return the reference to the node
  }

您能帮助引导我走向正确的方向吗？

Answer 1

正确的方法是将父节点与每个节点一起存储。如果您出于某种原因无法做到这一点，那么您应该使用 Map，而不是 Set。

在代码中的某个位置，您可以通过调用来填充此 map

mapParents.put(obj, parent)

然后您可以通过调用来检索父级

parent=mapParents.get(obj)

所有这一切，假设我正确理解您的要求。