【leetcode】133. Clone Graph

亦凉 2022-01-10 06:09 121阅读 0赞

**题目如下：**

> Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a `label` (`int`) and a list (`List[UndirectedGraphNode]`) of its `neighbors`. There is an edge between the given node and each of the nodes in its neighbors.
> 
>   
> OJ's undirected graph serialization (so you can understand error output):
> 
> 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 `#`.
> 
> 1.  First node is labeled as `0`. Connect node `0` to both nodes `1` and `2`.
> 2.  Second node is labeled as `1`. Connect node `1` to node `2`.
> 3.  Third node is labeled as `2`. Connect node `2` to node `2` (itself), thus forming a self-cycle.
> 
>  
> 
> Visually, the graph looks like the following:
> 
>     1
>           / \
>          /   \
>         0 --- 2
>              / \
>              \_/
> 
> Note: The information about the tree serialization is only meant so that you can understand error output if you get a wrong answer. You don't need to understand the serialization to solve the problem.

**解题思路：**深拷贝node。题目本身不难，由于所有节点的lable都是唯一的，因此需要保持已经创建过节点的lable，避免出现重复创建。另外节点存在self-cycle，所以遍历过的路径也需要保存。

**代码如下：**

# 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 None
            root = UndirectedGraphNode(node.label)
            queue = [(node,root)]
            dic = {}
            dic[root.label] = root
            dic_visit = {}
            while len(queue) > 0:
                n,r = queue.pop(0)
                if n.label in dic_visit:
                    continue
                for i in n.neighbors:
                    if i.label not in dic:
                        i_node = UndirectedGraphNode(i.label)
                        dic[i.label] = i_node
                    else:
                        i_node = dic[i.label]
                    r.neighbors.append(i_node)
                    queue.append((i, r.neighbors[-1]))
                dic_visit[n.label] = 1
    
            return root

转载于:https://www.cnblogs.com/seyjs/p/10214867.html