# 133. Clone Graph

## Description

See: <https://leetcode.com/problems/clone-graph/>

Given a graph, return a deep copy of it.

## Solution

This problem is a graph traversal problem. I used [BFS](/cs-theory-and-problems/algorithms/breadth-first-search-bfs.md#traversal) traversal to solve it. It uses the standard algorithm, but with the following changes:

* an extra variable, `current_clone`, is used to store the copied node.  When the `current_node` neighbors are traversed the standard check is done to see if the neighbor has been visited or not. If it has not been added then a new Node is created with the value. This is the copied value. In both cases the neighbor is added to the `current_clone` neighbors list.
* The visited hash value stores a copy of a Node. In the standard algorithm it is simply stores True. This hash stores the deep copy values.

```python
"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return node
        
        # note to self could also do queue = deque([node]) to condense the following two lines
        queue = deque()
        queue.append(node)
        
        # note: the visited hash creates a new Node as the value. This is the copy the question is asking for
        visited = {node.val: Node(node.val)}       
        while queue:
            current_node = queue.popleft()
            current_clone = visited[current_node.val]
            for neighbour in current_node.neighbors:
                if neighbour.val not in visited:
                    # Note: a new Node is created with the neighbour's val. This is the copy mechanism
                    visited[neighbour.val] = Node(neighbour.val)
                    queue.append(neighbour)
                # Note: The node that is appended is the one from the visited hash. This is the copy value
                current_clone.neighbors.append(visited[neighbour.val])
        # Note: return from the visited hash, as it holds the copied graph
        return visited[node.val]    
```


---

# 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://monica-granbois.gitbook.io/cs-theory-and-problems/problems/leetcode/133.-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.