Leetcode 133 Clone Graph
https://leetcode.com/problems/clone-graph
There will be 3 steps in the process
- Get all the nodes from the original graph
- Generate new nodes in the new graph and a mapping between the original node and the new node
- Connect the edge between new node and its new neighbor
For the first step we can use BFS
Let’s take a look at the solution
"""
# 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]