Baozi Training Leetcode solution 133: Clone Graph

包子面试培训

发布于 2019-12-12 16:33:17

3740

发布于 2019-12-12 16:33:17

文章被收录于专栏：包子铺里聊IT包子铺里聊IT

包子本周小道消息：

脸书被美国政府束缚了手脚，后知后觉的开始抄袭抖音，但是TikTok一统天下的趋势已经无法逆转，FB和Snap都要小心了。话说字节跳动都这么有钱了，去年revenue $7.5B, 今年会double，但还是打算再raise $2B (严肃，不是2b的意思）。小编有朋友早年加入字节，谈笑间樯橹灰飞烟灭，已经财富自由的人生就是放荡不羁呀！

Leetcode solution 133: Clone Graph

Blogger: https://blog.baozitraining.org/2019/11/leetcode-solution-133-clone-graph.html

Youtube: https://youtu.be/l-cPxs_TFkc

博客园: https://www.cnblogs.com/baozitraining/p/11965800.html

B站: https://www.bilibili.com/video/av77668992/

Problem Statement

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.

Example:

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.

Note:

The number of nodes will be between 1 and 100.
The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
You must return the copy of the given node as a reference to the cloned graph.

Problem link

Video Tutorial

You can find the detailed video tutorial here

Youtube
B站

Thought Process

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.

Solutions

BFS using queue

 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

DFS using recursion

 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

DFS using stack

 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 }