Блог

У меня возникли некоторые проблемы с пониманием ошибки в моем коде и причины ее истечения. Проблема заключается в создании клона ориентированного графа. Вот ссылка на вопрос: https://www.educative.io/m/clone-directed-graph

Мое решение использует очередь дважды. В первый раз я сопоставляю все узлы на графике с тем, каким будет соответствующий узел в клоне.

Во второй раз я использую очередь для перебора соседей, но получаю их соответствующие отображенные значения и добавляю их в список соседей для текущего узла, на котором я нахожусь.

Вот мой код.

 class Node {
  public int data;
  public List<Node> neighbors = new ArrayList<Node>();
  public Node(int d) {data = d;}
}

class graph {
  public static Node clone(Node root) {
    //use a queue to search the graph
    //use a haspmap to map graph node to clone node
    
    Queue<Node> q = new LinkedList<>();
    Map<Node, Node> map = new HashMap<>();
    q.add(root);
    map.put(root, new Node(root.data));

    while(!q.isEmpty()) {
      Node current = q.remove();
      
      for(Node temp : current.neighbors) {
        Node cloneTemp = new Node(temp.data);
        if(!map.containsKey(temp)) {
          q.add(temp);
          map.put(temp, cloneTemp);
        }
      }
    }
    q.add(root);
    while(!q.isEmpty()) {
      Node current = q.remove();
      Node currentClone = map.get(current);
        for(Node temp : current.neighbors) {
          Node mapNode = map.get(temp)
          if(!currentClone.neighbors.contains(mapNode)) {
            currentClone.neighbors.add(mapNode);
            q.add(temp);
          }
        }
      }
      
    return map.get(root);
  }
}