Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
Example:
Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.
Note:
- The number of nodes will be between 1 and 100.
- The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
- Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
- You must return the copy of the given node as a reference to the cloned graph.
Solutions
不管使用dfs还是bfs都需要一个哈希表map来存储原图中的节点和新图中的节点的一一映射。map的作用在于替代bfs和dfs中的visit数组，一旦map中出现了映射关系，就说明已经复制完成，也就是已经访问过了。
1. DFS
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution(object):
def cloneGraph(self, node):
"""
:type node: Node
:rtype: Node
"""
if not node:
return None
return self.dfs(node, {})
def dfs(self, node, map_):
if node in map_:
return map_[node]
o_node = Node(node.val, [])
map_[node] = o_node
for neighbor in node.neighbors:
o_node.neighbors.append(self.dfs(neighbor, map_))
return o_node
# Runtime: 56 ms, faster than 71.42% of Python online submissions for Clone Graph.
# Memory Usage: 12.8 MB, less than 68.75% of Python online submissions for Clone Graph.
2. BFS
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution(object):
def cloneGraph(self, node):
"""
:type node: Node
:rtype: Node
"""
if not node:
return None
queue = collections.deque()
queue.append(node)
map_ = {}
res_node = Node(node.val, [])
map_[node] = res_node
while queue:
cur_node = queue.popleft()
if not cur_node:
continue
for neighbor in cur_node.neighbors:
if neighbor not in map_:
map_[neighbor] = Node(neighbor.val, [])
queue.append(neighbor)
map_[cur_node].neighbors.append(map_[neighbor])
return res_node
# Runtime: 60 ms, faster than 39.95% of Python online submissions for Clone Graph.
# Memory Usage: 12.8 MB, less than 31.25% of Python online submissions for Clone Graph.