LeetCode #133 Clone Graph

Medium

Problem

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a label (int) and a list (List[UndirectedGraphNode]) of its neighbors. There is an edge between the given node and each of the nodes in its neighbors.

OJ’s undirected graph serialization (so you can understand error output):

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don’t need to understand the serialization to solve the problem.

Solution — BFS with Queue

Just use BFS approach by help from a queue for running through entire graph.

Solution — DFS with Stack

Just use DFS approach by help from a stack for running through entire graph.

Solution — DFS with Recursion

Use call stack for DFS approach. This one is cleaner and more beautiful.

Complexity

Three approaches are going to visit each node once and make their copies. Therefore, their time complexity are all O(n) if n denotes to count of nodes in the graph.

For space complexity, both queue and stack need O(n) for save all nodes. And the calling depth will be O(n) in worst case in recursion approach. Hence, all three approaches need O(n) extra space.