Глубокое копирование на Java

Question

У меня есть класс Java, узел следующим образом:

class Node
{
    public ArrayList<Node> nbrs;
}

Каждый объект Node содержит список всех своих соседей в ArrayList nbrs и ничего больше.

Теперь мне нужно написать функцию:

public Node copy( Node curr )

Эта функция должна выполнять глубокую копию всего графа с корнем в curr и возвращать эквивалентную копию для curr.

Я попытался реализовать конструктор копирования в классе Node следующим образом:

public Node( Node n )
{
    for( Node curr : n.nbrs )
        n.nbrs.add( new Node( curr  ));
}

Теперь я копирую Node n в моей функции копирования.

Но я обнаружил, что когда граф содержит циклы, этот код продолжает работать бесконечно.

Любая помощь в том, как мне решить эту проблему.

PS: Это вопрос интервью, с которым столкнулся мой друг, поэтому класс Node не может содержать больше переменных

Answer 1

Сохраните отображение между копируемыми старыми узлами и новыми в структуре данных, которая позволяет извлекать элементы на основе идентичности (то есть, которая извлекает объекты, если оператор == возвращает значение true). Примером этого может быть IdentityHashMap . Если вы создаете новый узел, то сохраните его в структуре данных.

Перед созданием нового Node из предыдущего только попытайтесь извлечь узел из структуры данных. Если у вас уже есть такой узел, добавьте найденный узел к родительскому. Если у вас нет такого узла, продолжайте его создание (и добавьте).

Answer 2

Если класс Node имеет parent, вы сможете проверить бесконечную рекурсию таким образом.Но это не так.Таким образом, вам нужно поддерживать некоторое состояние во время операции клонирования, Set, содержащее узлы, в которые вы в данный момент возвращаетесь.Отказаться от перехода в узел, который уже находится в Set.

Answer 3

Стандартный прием заключается в том, чтобы сначала создать все новые узлы и сохранить их на карте (от старых узлов до новых узлов). Затем за второй проход по всем узлам добавляются все ребра (путем добавления к n.nbrs.add).

Answer 4

В рекурсии нет базового регистра, кроме узла без соседей.
Дэниел Эрвикер предложил использовать Set, чтобы мы не добавляли одного и того же соседа дважды. Звучит хорошо, но как мы можем определить, находится ли узел в наборе? Реализация по умолчанию equals действительно просто ==, поэтому никакие два узла не будут считаться равными. Метод Set содержит метод equals для определения, был ли объект уже добавлен в набор. Мы добавляем поле id к узлу и затем реализуем boolean equals(Node other), проверяя равенство идентификаторов. Это должно заставить работать решение Set.

Answer 5

Если вы можете изменить класс Node и сделать его Serializable, то вы сериализуете / десериализуете объект и получаете новый граф объектов.

Пример кода для иллюстрации:

class Node implements Serializable 
{
    public List<Node> nbrs = new ArrayList<Node>();
}

Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
n1.nbrs.add(n2);
n2.nbrs.add(n1);
n2.nbrs.add(n3);
n3.nbrs.add(n2);

ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream dos = new ObjectOutputStream(baos);
dos.writeObject(n1);
dos.writeObject(n2);
dos.writeObject(n3);

ByteArrayInputStream bais = new ByteArrayInputStream(baos.toByteArray());
ObjectInputStream ois = new ObjectInputStream(bais);

Node n4 = (Node) ois.readObject();
Node n5 = (Node) ois.readObject();
Node n6 = (Node) ois.readObject();

На этом этапе у вас будет новый набор Node объектов, которые правильно ссылаются друг на друга.

Answer 6

Рассмотрите возможность сделать объекты Node неизменяемыми.В этом случае использование общего экземпляра не принесет вреда.