深度复制图形结构

Question

我有一个图形类，其中包含节点，每个节点可以连接到其他节点：

public class Node {
  List<Node> connections;
}

我想要制作整个图的深层拷贝。首先，我尝试创建一个类似于以下的拷贝构造函数：

public Node(Node other) {
  connections = new ArrayList<Node>();
  for (Node n : other.connections) { 
    connections.add(new Node(n));
  }
}

深度复制一个图形只需要这样做：

public Graph deepCopy () {
  Graph g = new Graph();
  g.nodes = new ArrayList<Node>();
  for (Node n : nodes) { 
    g.nodes.add(new Node(n));
  }
}

但是这样做会破坏节点之间的连接关系。我想知道是否有简单的方法可以解决这个问题？谢谢。

- JRR

Answer 1

问题在于你需要复制节点的身份，而不仅仅是它们的值。具体来说，当你复制某个节点时，你需要处理它所引用的节点的身份；这意味着一个复制构造函数或其他一些纯粹的本地复制机制无法胜任此工作，因为它只处理一个节点。我不确定这是否有任何意义，但我已经打了出来，我的退格键不起作用。

无论如何，你可以传递一些其他对象，它可以告诉你哪个新节点对应哪个旧节点。如果你想要花哨一点（谁不想？），你可以将其称为图同构。这可以是一个简单的映射。就像这段完全未经测试的代码：

// in Graph
public Graph deepCopy () {
  Graph g = new Graph();
  g.nodes = new ArrayList<Node>();
  Map<Node, Node> isomorphism = new IdentityHashMap<Node, Node>();
  for (Node n : nodes) { 
    g.nodes.add(n.deepCopy(isomorphism));
  }
  return g;
}

// in Node
public Node deepCopy(Map<Node, Node> isomorphism) {
    Node copy = isomorphism.get(this);
    if (copy == null) {
        copy = new Node();
        isomorphism.put(this, copy);
        for (Node connection: connections) {
            copy.connections.add(connection.deepCopy(isomorphism));
        }
    }
    return copy;
}

Sergii提到了使用序列化；当序列化遍历一个对象图时，它实际上执行的是一些非常相似的操作。

- Tom Anderson

---

对于那些不了解IdentityHashMap的人，请查看文档：http://docs.oracle.com/javase/7/docs/api/java/util/IdentityHashMap.html - Swapnil

@GonçaloRibeiro：是的，我想是这样。我写了一段时间，所以我不是绝对确定，但我认为我们在访问它们的连接之前将节点放入同构映射中的事实意味着循环被正确处理。 - Tom Anderson

Answer 2

是的，在Java（不仅仅是Java）中，可以使用内存序列化/反序列化来进行深度复制，如下所示

public static Object copy(Object orig) {
        Object obj = null;
        try {
            // Write the object out to a byte array
            ByteArrayOutputStream bos = new ByteArrayOutputStream();
            ObjectOutputStream out = new ObjectOutputStream(bos);
            out.writeObject(orig);
            out.flush();
            out.close();

            // Make an input stream from the byte array and read
            // a copy of the object back in.
            ObjectInputStream in = new ObjectInputStream(
                new ByteArrayInputStream(bos.toByteArray()));
            obj = in.readObject();
        }
        catch(IOException e) {
            e.printStackTrace();
        }
        catch(ClassNotFoundException cnfe) {
            cnfe.printStackTrace();
        }
        return obj;
    }

- Sergii Zagriichuk

---

请注意，如果您想为Graph类或像我一样的自定义BinaryTree类执行此操作，则必须在内部Node类和BinaryTree类上都编写“implements Serializable”。 - John61590

Answer 3

有点晚的输入。但我遇到了类似的问题，但找到了不同的解决方案。但不确定它是否万无一失。所以请随意评论，这样我就可以学习！

我有一个名为“Numbers”的类型，因为我没有创造性地命名东西。 每个“Numbers”类型的对象都有一个内部列表，可以携带其他类型“Numbers”的对象，每个对象都有一个附加的“Numbers”列表，每个列表都有...等等。

基本上，您可以创建类似于此的树形结构：

我通过在“Numbers”类内部使用递归复制构造函数解决了深拷贝问题。

Numbers类：

import java.util.ArrayList;

public class Numbers {

    private ArrayList<Numbers> numbers = new ArrayList<>();
    private int number;

    public Numbers(int number) {
        this.number = number;
    }

    public Numbers(Numbers numToCopy) {
        this.number = numToCopy.getNumber();
        ArrayList<Numbers> list = numToCopy.getNumbers();
        for(int i = 0; i < list.size(); i++) {
            Numbers n = new Numbers(list.get(i));
            numbers.add(n);
        }
    }

    public void addNumber(Numbers i) {
        numbers.add(i);
    }

    public ArrayList<Numbers> getNumbers() {
        return numbers;
    }

    public void setNumber(int i) {
        this.number = i;
    }

    public int getNumber() {
        return number;
    }

    public ArrayList<Numbers> getAllNumbers(ArrayList<Numbers> list) {
        int size = numbers.size();
        list.addAll(numbers);
        for(int i = 0; i < size; i++) {
            numbers.get(i).getAllNumbers(list);
        }
        return list;
    }

}

用法：

import java.util.ArrayList;

public class NumbersTest {

    public NumbersTest() {

    }

    public static void main(String[] args) {
        Numbers num0 = new Numbers(0);
        Numbers num1 = new Numbers(1);
        Numbers num2 = new Numbers(2);
        Numbers num3 = new Numbers(3);
        Numbers num4 = new Numbers(4);
        Numbers num5 = new Numbers(5);
        Numbers num6 = new Numbers(6);

        num0.addNumber(num1);
        num0.addNumber(num2);

        num1.addNumber(num3);
        num1.addNumber(num4);

        num2.addNumber(num5);
        num2.addNumber(num6);

        num4.addNumber(num6);

        //Deep copy here!
        Numbers numCopy = new Numbers(num0);
        //Change deep down in graph of original
        num0.getNumbers().get(0).getNumbers().get(1).getNumbers().get(0).setNumber(799);
        //Printout of copy to show it was NOT affected by change in original.
        for(Numbers n : numCopy.getAllNumbers(new ArrayList<Numbers>())) {
            System.out.println(n.getNumber());
        }

    }

}

使用代码显示，更改原始num0对象“图形”深处的内容不会更改其副本。

图中有两个六（6），这是可以的，因为它们位于不同的分支上。 缺点是如果相同的数字通过其中一条路径重复出现，例如在第一个1下方有一个（1）。那么它将最终陷入无限循环。

请评论！:)

- brat