Leetcode 133 Clone Graph
https://leetcode.com/problems/clone-graph/description
We can conquer this problem by a couple steps:
- Get the all the nodes in the original graph with BFS
- Clone each node and keep a map between the original node and the new node
- Create the edge between in the new graph
"""
# 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 []
"""
from typing import Optional
class Solution:
def get_all_nodes(self, node):
visited = set([node])
queue = collections.deque([node])
while queue:
current = queue.popleft()
for neighbor in current.neighbors:
if neighbor in visited:
continue
visited.add(neighbor)
queue.append(neighbor)
return visited
def get_map(self, nodes):
map = {}
for node in nodes:
map[node] = Node(node.val)
return map
def add_edge(self, nodes, map):
for node in nodes:
new_node = map[node]
for neighbor in node.neighbors:
new_node.neighbors.append(map[neighbor])
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
nodes = self.get_all_nodes(node)
map = self.get_map(nodes)
self.add_edge(nodes, map)
return map[node]
Pingback: Breadth First Search(BFS) - Leetcode Solution