首页 > itarticle > leetcode_clone graph

leetcode_clone graph

admin 11月 13, 2020 0

Clone Graph

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.
（深度拷贝图）

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.

Example:

1. DFS (递归)

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class :
    def dfs(self, node):
        for _node in node.neighbors:
            if _node not in self.map_dict:
                copy_neighbor = Node(_node.val, [])
                self.map_dict[_node] = copy_neighbor
                self.map_dict[node].neighbors.append(copy_neighbor)
                self.dfs(_node)
            else:
                self.map_dict[node].neighbors.append(self.map_dict[_node])        
        return
            
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        self.map_dict = {}
        copy_node = Node(node.val, [])
        self.map_dict[node] = copy_node
        self.dfs(node)
        
        return copy_node

2. DFS (栈)

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class :            
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        map_dict = {}
        copy_node = Node(node.val, [])
        map_dict[node] = copy_node
        
        stack = [node]
        while stack:
            _node = stack.pop()
            for neighbor in _node.neighbors:
                if neighbor not in map_dict:
                    copy_neignbor = Node(neighbor.val, [])
                    map_dict[neighbor] = copy_neignbor
                    map_dict[_node].neighbors.append(copy_neignbor)
                    stack.append(neighbor)
                else:
                    map_dict[_node].neighbors.append(map_dict[neighbor])
                
        return copy_node

3. BFS (队列)

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class :        
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        
        map_dict = {}
        copy_node = Node(node.val, [])
        map_dict[node] = copy_node
        
        queue = [node]
        while queue:
            _node = queue.pop(0)
            for neighbor in _node.neighbors:
                if neighbor not in map_dict:
                    copy_neignbor = Node(neighbor.val, [])
                    map_dict[neighbor] = copy_neignbor
                    map_dict[_node].neighbors.append(copy_neignbor)
                    queue.append(neighbor)
                else:
                    map_dict[_node].neighbors.append(map_dict[neighbor])
                
        return copy_node