MediumBlind75GraphDFSBFSHash Table
Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy of the graph.
Examples
Input
adjList = [[2,4],[1,3],[2,4],[1,3]]
Output
[[2,4],[1,3],[2,4],[1,3]]
There are 4 nodes in the graph. Node 1's neighbors are 2 and 4.
Input
adjList = [[]]
Output
[[]]
The graph has one node with no neighbors.
Constraints
- •
The number of nodes in the graph is in the range [0, 100] - •
1 <= Node.val <= 100 - •
Node.val is unique for each node. - •
Number of edges is in the range [0, 100].
Approaches
Use BFS to traverse and clone each node.
CodeT: O(V + E) | S: O(V)
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
from collections import deque
def cloneGraph(node):
if not node:
return None
clones = {node: Node(node.val)}
queue = deque([node])
while queue:
curr = queue.popleft()
for neighbor in curr.neighbors:
if neighbor not in clones:
clones[neighbor] = Node(neighbor.val)
queue.append(neighbor)
clones[curr].neighbors.append(clones[neighbor])
return clones[node]Use DFS to traverse and clone each node.
CodeT: O(V + E) | S: O(V)
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def cloneGraph(node):
if not node:
return None
clones = {}
def dfs(curr):
if curr in clones:
return clones[curr]
clone = Node(curr.val)
clones[curr] = clone
for neighbor in curr.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)Same DFS approach with cleaner implementation.
Diagram
Node 1 -> [2,4]
Clone: create Node(1), then clone neighbors
Node 2 -> [1,3], Node 3 -> [2,4], Node 4 -> [1,3]
Deep copy with same structure
CodeT: O(V + E) | S: O(V)
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def cloneGraph(node):
if not node:
return None
visited = {}
def clone(curr):
if curr in visited:
return visited[curr]
new_node = Node(curr.val)
visited[curr] = new_node
for neighbor in curr.neighbors:
new_node.neighbors.append(clone(neighbor))
return new_node
return clone(node)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| BFS with Hash Map | O(V + E) | O(V) | Use BFS to traverse and clone each node. |
| DFS with Hash Map | O(V + E) | O(V) | Use DFS to traverse and clone each node. |
| Optimized DFS | O(V + E) | O(V) | Same DFS approach with cleaner implementation. |
BFS with Hash Map
T: O(V + E)S: O(V)
Use BFS to traverse and clone each node.
DFS with Hash Map
T: O(V + E)S: O(V)
Use DFS to traverse and clone each node.
Optimized DFS
T: O(V + E)S: O(V)
Same DFS approach with cleaner implementation.
Common Mistakes
Creating shallow copies instead of deep copies
Not handling cycles in the graph
Forgetting to add edges to the cloned node's neighbors