Clone Graph

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

How we serialize an undirected graph:

Nodes are labeled uniquely.

给定一个图的节点，并且图示连通图，意味着每一个节点都是联通的，可以通过给定的节点找到所有的节点。

Solution 1

首先利用BFS 进行图的每一个节点遍历，然后在判断节点是否遍历过的同时把节点的副本保存到以当前节点为Key的哈希表中。第二步就是复制所有节点的对应的邻居节点。时间复杂度：O(E + V) nodes (V) plus all edges (E)

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def cloneGraph(self, node):
        if node == None:
            return node
        dict = {}
        q = collections.deque([])
        q.append(node)

        while len(q) > 0:
            n = q.popleft()
            if n not in dict:
                dict[n] = UndirectedGraphNode(n.label)
                for c in n.neighbors:
                    q.append(c)

        # copy child nodes.
        for key in dict:
            for child in key.neighbors:
                dict[key].neighbors.append(dict[child])

        return dict[node]

Solution 2

也可以利用DFS，这里比较巧妙的步骤是，可以在边Copy数据到HashMap中的时候，可以维护邻居节点的关系。O(E + V) since you traverse all nodes (V) plus all edges (E)

class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.dict = {}

    def cloneGraph(self, node):
        # write your code here
        if node == None:
            return node
        root = UndirectedGraphNode(node.label)
        self.dict[node] = root
        self.dfs(node)
        return root

    def dfs(self, node):
        if node == None:
            return
        for child in node.neighbors:
            if child not in self.dict:
                self.dict[child] = UndirectedGraphNode(child.label)
                self.dfs(child)
            self.dict[node].neighbors.append(self.dict[child])

Solution 3

可以直接利用一层递归的方法实现，不太好想。首先就是递归的定义就是每次返回的复制的节点。O(E + V) since you traverse all nodes (V) plus all edges (E)

# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.dict = {}

    def cloneGraph(self, node):
        if node == None:
            return None
        if node in self.dict:
            return self.dict[node]
        root = UndirectedGraphNode(node.label)
        self.dict[node] = root
        for item in node.neighbors:
            root.neighbors.append(self.cloneGraph(item))
        return root