Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
- First node is labeled as
0. Connect node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
# Definition for a undirected graph node
# class UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors = []
这个题的思路是用BFS 或者 DFS, 然后这个题目我们加一个dictionary去节省反复进入某个loop里面.
1. Constraints
1) node id is unique for all nodes
2) 可能为empty
2. Ideas
T: O(n) S: O(n)
1) d = {}去save original node and new node created, if created, then dont need to keep looping.
2) otherwise, create root and recursively calling root.neighbors
T: O(n) . S: O(n)
1) 还是用visited = {} 去保存original node 和new node， 不过先不管neighbours，先copy所有的node
2） copy 所有node 的neighbors
3. code
UndirectedGraphNode:
# def __init__(self, x):
# self.label = x
# self.neighbors class Solution:
def cloneGraph(self, node):
def dfs(node):
if not node: return
if node in d: return d[node]
root = UndirectedGraphNode(node.label)
d[node] = root
for each in node.neighbors:
if each in d:
root.neighbors.append(d[each])
else:
root.neighbors.append(dfs(each))
return root
d = {}
return dfs(node)
2. Code
# Using BFS
class Node:
def __init__(self, x, neighbors):
self.val = x
self.neighbors = neighbors import collections
class Solution:
def cloneGraph(self, node):
if not node: return
visited, root, queue = {}, node, collections.deque([node])
while queue: # copy nodes
popNode = queue.popleft()
if popNode not in visited:
visited[popNode] = Node(popNode.val, [])
for each in popNode.neighbors:
queue.append(each)
# copy neighbors
for oriNode, copyNode in visited.items():
for each in oriNode.neighbors:
copyNode.neighbors.append(visited[each])
return visited[root]