Clone Graph

Clone an undirected graph. Each node in the graph contains alabeland a list of itsneighbors.

OJ's undirected graph serialization:

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
         / \
         \_/

Solution:

General: BFS = Queue + Hashmap

For this problem:

先克隆点，再克隆边。

Use BFS to clone nodes first (make duplicate nodes of original nodes), then copy the neighboring relationship.

Hashmap<old node, copied node>.

First BFS to create a hashmap of old nodes to new nodes.

Then go through the hashmap, and add the neighboring relationship to new nodes according to old node.

Time Complexity: O( V + E )

Space: O(V)

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if node == None:
            return node

        # key is original node, value is cloned node
        visited = {node: UndirectedGraphNode(node.label)}
        q = [node]

        # clone all the unique labeled graph nodes
        while q:
            new_q = []
            while q:
                nd = q.pop(0)
                for neighborNode in nd.neighbors:
                    if neighborNode not in visited:
                        visited[neighborNode] = UndirectedGraphNode(neighborNode.label)
                        new_q.append(neighborNode)
            q = new_q

        # clone all the neighbors for all the cloned nodes
        for key in visited:
            for neighborNode in key.neighbors:
                clonedNeighborNode = visited[neighborNode]
                visited[key].neighbors.append(clonedNeighborNode)

        return visited[node]