越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/clone-graph/

We use breadth first search (BFS) to traverse and duplicate the graph. In order to prevent cloning a vertex twice, we use a dictionary oldToNew to map vertices from the original graph to cloned vertices in the new graph. Note that the key set of the oldToNew dict is just the discovered set in the original BFS algorithm

When we see a vertex that hasn’t been cloned, we clone it and save it into oldToNew. We build the edges (u, v) when we discover v via u.

The time complexity is the same as BFS’s, i.e. $\O(n+m)$. Because we need the dictionary to store the mapping of all vertices, the space complexity is $\O(n)$.

我们使用广度优先搜索(BFS)来复制整张图。为了防止重复复制相同的顶点,我们使用一个字典 oldToNew 将原图中的顶点映射到新图中的结点;这个字典的 key set 即是 BFS 的 discovered 集合。

当我们看到一个未被复制的顶点时,我们复制它,存入 oldToNew。我们在通过 u 发现 v 时就建立新图中的边 (u, v)

算法的时间复杂度与 BFS 相同,即 $\O(n+m)$;由于需要一个字典存储所有新旧顶点的对应关系,空间复杂度为 $\O(n)$。

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
from collections import deque

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        self.oldToNew = dict()
        return self._bfs(node)
    
    def _bfs(self, start):
        newStart = Node(start.val, [])
        self.oldToNew[start] = newStart
        q = deque([start])
        while q:
            u = q.popleft()
            newU = self.oldToNew[u]
            for v in u.neighbors:
                if v not in self.oldToNew:
                    q.append(v)
                    self.oldToNew[v] = Node(v.val, [])
                newU.neighbors.append(self.oldToNew[v])
        return newStart