# Clone Graph

Clone an undirected graph. Each node in the graph contains a`label`and a list of its`neighbors`.

**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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://bhabs.gitbook.io/prepbook/coding/clone-graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.