traverse graph (Breadth First Search)
copy using HashMap
# Definition for a undirected graph node
# class UndirectedGraphNode(object):
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution(object):
def cloneGraph(self, node):
"""
:type node: UndirectedGraphNode
:rtype: UndirectedGraphNode
"""
if node is None:
return None
#if graph is not empty, make a copy of the first node
cloned_node=UndirectedGraphNode(node.label)
#create a hashmap with key=node in the original graph,value=cloned node
cloned={node:cloned_node}
#store the next level of nodes to be visited
queue=[node]
while queue:
current=queue.pop()
#loop through the neighbours of the current node
for neighbor in current.neighbors:
#if the neighbor node hasn't been cloned before, make a clone
if neighbor not in cloned:
queue.append(neighbor)
cloned_neighbor=UndirectedGraphNode(neighbor.label)
cloned[neighbor]=cloned_neighbor
#attach the created neighbors to the current graph node
cloned[current].neighbors.append(cloned[neighbor])
return cloned[node]
133. Clone Graph
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 原题 克隆一张无向图,图中的每个节点包含一个 label 和一个表 neighbors。你的程序需要返回一个经过深...
- 题意:克隆一个无向图。 思路:因为是克隆所以需要一个map来存储克隆的映射关系,我们可以从给定的第一个节点向它的n...
- 编译部署 参考:https://github.com/ceph/ceph/ 写在前面 一定要给足够的磁盘空间,建议...