# 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](https://monica-granbois.gitbook.io/cs-theory-and-problems/algorithms/breadth-first-search-bfs#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]    
```