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

Method 1: 2 * O(nlogn) and O(n) space for building the dict of visited/refDict

# 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 not node:
            return None
        #===================================
        # Do a BFS search of the Graph  
        #===================================
        from collections import deque    
        Q = deque()    
        Q.append(node)
        refDict = {}
        clonedHead = None

        while len(Q) > 0:
            n = Q.popleft()
            clonedNode = UndirectedGraphNode(n.label) # create a cloned Node

            # preserve the old node label to the cloned node reference. This will be used later for re-adjustment
            if n not in refDict:
                refDict[n.label] = clonedNode

            # This is just one time, so that we can return the cloned Node head reference    
            if clonedHead is None:
                clonedHead = clonedNode

            for nn in n.neighbors:
                if nn.label not in refDict:
                    #print 'nn: ', nn.label
                    Q.append(nn)

                # preserve the reference of old neighbors in the cloned neighbors list[]
                # this will be re-adjusted later
                clonedNode.neighbors.append(nn) 

        #========================================================
        # Now walk over the cloned list and adjust the neighbors
        # Second BFS
        #========================================================
        Q.clear()
        Q.append(clonedHead)

        visited = {}

        while len(Q) > 0:
            cn = Q.popleft()
            if cn.label not in visited:
                visited[cn.label] = 1

            # replace all the old neighbor reference with clonedNode reference
            cn.neighbors = [refDict[x.label] for x in cn.neighbors]

            for cnn in cn.neighbors:
                if cnn.label not in visited:
                    Q.append(cnn)

        return clonedHead

Method 2: O(nlogn) for BFS and O(n) to store the visited. The second traversal is not needed

# 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 not node:
            return None
        #===================================
        # Do a BFS search of the Graph  
        #===================================
        from collections import deque    
        Q = deque()    
        Q.append(node)
        visited = {}

        clonedNode = UndirectedGraphNode(node.label) # create a cloned Node, the root
        visited[node.label] = clonedNode

        while len(Q) > 0:
            n = Q.popleft()

            for nn in n.neighbors:
                if nn.label not in visited:
                    #print 'nn: ', nn.label
                    Q.append(nn)
                    visited[nn.label] = UndirectedGraphNode(nn.label)

                # update the neighbors of the cloned node; 
                # the corresponding clone node of the one which got popped from Queue
                visited[n.label].neighbors.append(visited[nn.label]) 

        return clonedNode