克隆图的算法 [英] Algorithm to clone a graph

问题描述

克隆树的算法非常简单，我们可以为此进行预遍历。有没有有效的算法来克隆图？

Algorithm to clone a tree is quite easy, we can do pre-order traversal for that. Is there an efficient algorithm to clone a graph?

我尝试了一种类似的方法，并得出结论，我们需要维护新图中已添加的节点的哈希图，否则将出现重复的节点，因为节点可以有很多父母。

I tried a similar approach, and concluded we need to maintain a hash-map of nodes already added in the new graph, else there will be duplication of nodes, since one node can have many parents.

推荐答案

只需进行深度优先搜索并在访问每个节点时将其复制即可。如您所说，您需要某种方式将原始图中的节点映射到相应的副本，以便可以正确连接循环和交叉边的副本。

It suffices to do a depth first search and copy each node as it's visited. As you say, you need some way of mapping nodes in the original graph to corresponding copies so that copies of cycle and cross edges can be connected correctly.

此图也足以记住DFS中已访问的节点。

This map also suffices to remember nodes already visited in the DFS.

因此，在Java中，您会有类似的东西：

So in Java you'd have something like:

class Node {

  // Contents of node...
  Data data;

  // ... member declarations like array of adjacent nodes
  final ArrayList<Node> children = new ArrayList<>();

  // Recursive graph walker for copying, not called by others.
  private Node deepCloneImpl(Map<Node, Node> copies) {
    Node copy = copies.get(this);
    if (copy == null) {
      copy = new Node(data);
      // Map the new node _before_ copying children.
      copies.put(this, copy);
      for (Node child : children)
        copy.children.add(child.deepCloneImpl(copies));
    }
    return copy;
  }

  public Node deepClone() {
    return deepCloneImpl(new HashMap<Node, Node>());
  }
}

请注意，您不要希望为 Node 覆盖等价或 hashCode 。包含副本的映射依赖于 Object 定义的引用相等。

Note that you don't want to override equals or hashCode for Node. The map containing copies relies on reference equality as defined by Object.

另一种方法是放置一个附加字段在每个指向副本的节点中是否存在副本，否则为null。这仅通过另一种方法来实现地图。但这需要在图形上进行两次传递：一次进行复制，另一次清除这些地图字段以供将来重用。

A different approach is to put an additional field in each node that points to the copy if there is one and is null otherwise. This merely implements the map by another method. But it requires two passes over the graph: one to make the copy and another to clear these map fields for future re-use.

这篇关于克隆图的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！