# Clone [[graph|Graph]]
Creating deep copy of a connected graph.
https://leetcode.com/problems/clone-graph/
## Solution 1: [[dfs|DFS]]
```python
table = dict[Node, Node]()
def dfs(node: Optional['Node']) -> Optional['Node']:
nonlocal table
if not node or node in table:
return
clone = Node(node.val, [])
table[node] = clone
for neighbor in node.neighbors:
clone.neighbors.append(
table[neighbor] if neighbor in table else
dfs(neighbor)
)
return clone
return dfs(node)
```
## Solution 2: [[bfs|BFS]]
```python
if not node:
return
table = dict[Node, Node]()
root = node
queue = deque[Node]([root])
while queue:
node = queue.popleft()
if node in table:
continue
clone = Node(node.val, [])
table[node] = clone
for neighbor in node.neighbors:
if neighbor in table:
table[neighbor].neighbors.append(clone)
clone.neighbors.append(table[neighbor])
else:
queue.append(neighbor)
return table[root]
```