9

我有一个带有节点的图形类，每个节点都可以连接到其他节点：

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));
  }
}

但这不起作用，因为这破坏了节点之间的连接关系。我想知道是否有人建议以简单的方式做到这一点？谢谢。

4

3 回答 3

15

问题是您需要复制节点的身份，而不仅仅是它们的值。具体来说，当您复制某个节点时，您需要处理它所引用的节点的身份；这意味着复制构造函数或其他某种纯本地复制机制无法完成这项工作，因为它一次只处理一个节点。我不确定这是否有意义，但我已经输入了它，但我的退格键不起作用。

无论如何，您可以做的是传递一些其他对象，这些对象可以告诉哪个新节点对应于哪个旧节点。如果您想变得花哨（谁不想呢？），您可以将其称为graph isomorphism。这可以像地图一样简单。就像在这个完全未经测试的代码中一样：

// 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 提到使用序列化；序列化在遍历对象图时实际上做了非常相似的事情。

于 2012-10-14T20:40:49.630 回答
6

是的，java中的深拷贝（不仅在java中）可以使用serialization/deserialization 这样的内存进行

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;
    }
于 2012-10-14T20:12:36.360 回答
0

有点晚输入。但是我遇到了类似的问题，但得到了不同的解决方案。但不确定它是否防弹。所以请随时发表评论，让我学习！

我有一个名为“数字”的类型，因为我没有创意命名的东西。每个“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 )。然后它将以无限循环结束。

请发表评论！:)

于 2019-10-30T20:06:37.933 回答