int) and a list (List[Node]) of its neighbors.
Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
Explanation:
Node 1‘s value is 1, and it has two neighbors: Node 2 and 4.
Node 2‘s value is 2, and it has two neighbors: Node 1 and 3.
Node 3‘s value is 3, and it has two neighbors: Node 2 and 4.
Node 4‘s value is 4, and it has two neighbors: Node 1 and 3.
Problem link
You can find the detailed video tutorial here
It‘s a basic graph problem that can be solved in 3 different ways: BFS
using queue, DFS using recursion, DFS using stack(very similar to BFT
using queue). The trick is using a map to keep a one-to-one mapping
between the old nodes and the copied nodes, meanwhile, we can also use
the map to avoid a cycle when performing BFS or DFS.
1 public Node cloneGraphBFS(Node node) { 2 if (node == null) { 3 return node; 4 } 5 6 Map<Node, Node> lookup = new HashMap<>(); 7 8 Queue<Node> q = new LinkedList<>(); 9 q.add(node); 10 lookup.put(node, new Node(node.val, new ArrayList<>())); 11 12 while (!q.isEmpty()) { 13 Node cur = q.poll(); 14 15 for (Node n : cur.neighbors) { 16 Node copiedNeighbor = null; 17 18 if (!lookup.containsKey(n)) { 19 // the neighbors would be populated later when it‘s popped out from the queue 20 copiedNeighbor = new Node(n.val, new ArrayList<>()); 21 lookup.put(n, copiedNeighbor); 22 q.add(n); 23 } else { 24 copiedNeighbor = lookup.get(n); 25 } 26 lookup.get(cur).neighbors.add(copiedNeighbor); 27 } 28 } 29 return lookup.get(node); 30 }
Time Complexity: O(N)
Space Complexity: O(N) the extra queue and map
1 public Node cloneGraphDFSWithRecursion(Node node) { 2 if (node == null) { 3 return node; 4 } 5 Map<Node, Node> lookup = new HashMap<>(); 6 return this.cloneGraphHelper(node, lookup); 7 } 8 9 /** 10 * A dfs helper using recursion to make a copy of each node recursively via neighbors 11 * @param node 12 * @param lookup 13 * @return the copied node of Node 14 */ 15 private Node cloneGraphHelper(Node node, Map<Node, Node> lookup) { 16 if (node == null) { 17 return node; 18 } 19 20 if (lookup.containsKey(node)) { 21 return lookup.get(node); 22 } 23 24 Node copiedNode = new Node(node.val, new ArrayList<>()); 25 lookup.put(node, copiedNode); 26 for (Node n : node.neighbors) { 27 Node copiedN = this.cloneGraphHelper(n, lookup); 28 copiedNode.neighbors.add(copiedN); 29 } 30 return copiedNode; 31 }
Time Complexity: O(N)
Space Complexity: O(N) the extra map
1 // exactly the same as BFS except used a stack to mimic the recursion, technically any BFS can be written 2 // in DFS by using a stack 3 public Node cloneGraphDFSUsingStack(Node node) { 4 if (node == null) { 5 return node; 6 } 7 Map<Node, Node> lookup = new HashMap<>(); 8 Node t = new Node(node.val, new ArrayList<>()); 9 lookup.put(node, t); 10 11 Stack<Node> stack = new Stack<>(); 12 stack.push(node); 13 14 while (!stack.isEmpty()) { 15 Node cur = stack.pop(); 16 17 for (Node n : cur.neighbors) { 18 Node copiedNeighbor = null; 19 if (!lookup.containsKey(n)) { 20 copiedNeighbor = new Node(n.val, new ArrayList<>()); 21 stack.push(n); 22 lookup.put(n, copiedNeighbor); 23 } else { 24 copiedNeighbor = lookup.get(n); 25 } 26 lookup.get(cur).neighbors.add(copiedNeighbor); 27 } 28 } 29 30 return lookup.get(node); 31 }
Time Complexity: O(N)
Space Complexity: O(N) the extra queue and stack
The main test method
1 public static void main(String[] args) { 2 CloneGraph cg = new CloneGraph(); 3 4 // construct the example graph 5 Node n1 = new Node(1, new ArrayList<>()); 6 Node n2 = new Node(2, new ArrayList<>()); 7 Node n3 = new Node(3, new ArrayList<>()); 8 Node n4 = new Node(4, new ArrayList<>()); 9 n1.neighbors.addAll(Arrays.asList(new Node[]{n2, n4})); 10 n2.neighbors.addAll(Arrays.asList(new Node[]{n3, n3})); 11 n3.neighbors.addAll(Arrays.asList(new Node[]{n2, n4})); 12 n4.neighbors.addAll(Arrays.asList(new Node[]{n1, n3})); 13 // add a self cycle 14 n1.neighbors.addAll(Arrays.asList(new Node[]{n1})); 15 16 // expect the same BFS order print out 17 Utilities.printGraphBFS(n1); 18 Node copiedN1 = cg.cloneGraphBFS(n1); 19 Utilities.printGraphBFS(copiedN1); 20 } 21 22 /** 23 * print out a graph in BFS node, note it could be a cycle, so it‘s not really the topological order 24 * 25 * 1 ----- 2 26 * | | 27 * 4 ----- 3 28 * @param node 29 */ 30 public static void printGraphBFS(CloneGraph.Node node) { 31 if (node == null) { 32 return; 33 } 34 35 Set<CloneGraph.Node> visited = new HashSet<>(); 36 Queue<CloneGraph.Node> queue = new LinkedList<>(); 37 queue.add(node); 38 System.out.println(node.val); 39 visited.add(node); 40 41 while (!queue.isEmpty()) { 42 CloneGraph.Node cur = queue.poll(); 43 for (CloneGraph.Node n : cur.neighbors) { 44 if (!visited.contains(n)) { 45 queue.add(n); 46 System.out.println(n.val); 47 visited.add(n); 48 } 49 } 50 } 51 }
Baozi Leetcode solution 133: Clone Graph
原文：https://www.cnblogs.com/baozitraining/p/11965800.html