[LeetCode]Clone Graph

题目描述:

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

OJ's undirected graph serialization:

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 #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
Second node is labeled as 1. Connect node 1 to node 2.
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
         / \
         \_/

题目大意:

克隆一个无向图。图中的每个节点包含一个标签及其邻居的列表。

OJ对于无向图的序列化:

节点的标签是唯一的。

我们使用 井号(#) 作为节点的分隔符,使用 逗号(,)作为节点标签以及每个邻居之间的分隔符。

例如,考虑下面的序列化图 {0,1,2#1,2#2,2}

上图包含3个节点,因而包含3个#分隔符。

第一个节点标签为0,节点0与节点1,节点2相连。
第二个节点标签为1, 节点1与节点2相连。
第三个节点标签为2,节点2与节点2相连(其本身),因而形成一个自环。

可视化地,上面的图看起来像这样:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

 

解题思路:

本题考查图的深拷贝

通过BFS或者DFS遍历图,利用字典维护标号与新增节点之间的映射关系。

Python代码:

# 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 is None:
            return None
        needle = UndirectedGraphNode(node.label)
        nodeDict = {node.label : needle}
        stack = [node]
        while stack:
            top = stack.pop()
            cnode = nodeDict[top.label]
            for n in top.neighbors:
                if n.label not in nodeDict:
                    nodeDict[n.label] = UndirectedGraphNode(n.label)
                    stack.append(n)
                cnode.neighbors.append(nodeDict[n.label])
        return needle

 

本文链接:http://bookshadow.com/weblog/2015/08/10/leetcode-clone-graph/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论