133.Clone-Graph

133. Clone Graph

题目地址

https://leetcode.com/problems/clone-graph/

https://www.jiuzhang.com/solutions/clone-graph/

题目描述

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

Test case format:

For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

代码

Approach #1 DFS

class Solution {
    private HashMap <Node, Node> visited = new HashMap <> ();
    public Node cloneGraph(Node node) {
        if (node == null)     return node;

        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        Node cloneNode = new Node(node.val, new ArrayList());
        visited.put(node, cloneNode);

        for (Node neighbor: node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

Approach #2 BFS

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null)   return node;

        HashMap<Node, Node> visited = new HashMap();
        visited.put(node, new Node(node.val, new ArrayList()));

        LinkedList<Node> queue = new LinkedList<Node> ();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node n = queue.remove();

            for (Node neighbor: n.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // Clone the neighbor and put in the visited, if not present already
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList()));
                    // Add the newly encountered node to the queue.
                    queue.add(neighbor);
                }
                // Add the clone of the neighbor to the neighbors of the clone node "n".
                visited.get(n).neighbors.add(visited.get(neighbor));
            }
        }

        // Return the clone of the node from visited.
        return visited.get(node);
    }
}

// 九章

Approach #1

class UndirectedGraphNode {
  int label;
  ArrayList<UndirectedGraphNode> neighbors;
  UndirectedGraphNode(int x) { 
    label = x; 
    neighbors = new ArrayList<UndirectedGraphNode>(); 
  }
};

public class Solution {
    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return node;

    ArrayList<UndirectedGraphNode> nodes = getNodes(node);

    HashMap<UndirectedGraphNode, UndirectedGraphNode> mapping = new HashMap<>();
    for (UndirectedGraphNode n : nodes) {
      mapping.put(n, new UndirectedGraphNode(n.label));
    }

    for (UndirectedGraphNode n : nodes) {
      UndirectedGraphNode newNode = mapping.get(n);
      for (UndirectedGraphNode neighbor : n.neighbors) {
        UndirectedGrapNode newNeighbor = mapping.get(neighbor);
        newNode.neighbors.add(newNeighbor);
      }
    }

    return mapping.get(node);
  }

  private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
    Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    HashSet<UndirectedGraphNode> set = new HashSet<>();

    queue.offer(node);
    set.add(node);
    while (!queue.isEmpty()) {
      UndirectedGraphNode head = queue.poll();
      for (UndirectedGraphNode neighbor : head.neighbors) {
        if (!set.contains(neighbor)) {
          set.add(neighbor);
          queue.offer(neighbor);
        }
      }
    } 

    return new ArrayList<UndirectedGraphNode>(set);
  }
}

Approach #2

public class Solution {
  public UndirectedGraphNode cloneGraph(UndirectedGraphNode noe) {
    if (node == null) return null;

    ArrayList<UndirectedGraphNode> nodes = new ArrayList<UndirectedGraphNode>();
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

    nodes.add(node);
    map.put(node, new UndirectedGraphNode(node.label));

    int start = 0;
    while (start < nodes.size()) {
      UndirectedGraphNode head = nodes.get(start++);
      for (int i = 0; i < head.neighbors.size(); i++) {
        UndirectedGraphNode neighbor = head.neighbors.get(i);
        if (!map.containsKey(neighbor)) {
          map.put(neighbor, new UndirectedGraphNode(neighbor.label));
          nodes.add(neighbor);
        }
      }
    }

    for (int i = 0; i < nodes.size(); i++) {
      UndirectedGraphNode newNode = map.get(nodes.get(i));
      for (int j = 0; j < nodes.get(i).neighbors.size(); j++) {
        newNode.neighbors.add(map.get(nodes.get(i).neighbors.get(j)));
      }
    }

    return map.get(node);
  }
}

Using Stack

class StackElement {
  public UndirectedGraphNode node;
  public int neighborIndex;
  public StackElement(UndirectedGraphNode node, int neighborIndex) {
    this.node = node;
    this.neighborIndex = neighborIndex;
  }
}

private ArrayList<UndirectedGraphNode> getNodes(UndirectedGraphNode node) {
  Stack<StackElement> stack = new Stack<StackElement>();
  HashSet<UndirectedGraphNode> set = new HashSet<>();
  stack.push(new StackElement(node, -1));
  set.add(node);

  while (!stack.isEmpty()) {
    StackElement current = stack.peek();
    current.neighborIndex++;

    if (current.neighborIndex == current.node.neighbors.size()) {
      stack.pop();
      continue;
    }

    UndirectedGraphNode neighbor = current.node.neighbors.get(current.neighborIndex);

    if (set.contains(neighbor))    continue;

    stack.push(new StackElement(neighbor, -1));
    set.add(neighbor);
  }

  return new ArrayList<UndirectedGraphNode>(set);
}