-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path133_Clone_Graph.py
More file actions
86 lines (74 loc) · 2.5 KB
/
133_Clone_Graph.py
File metadata and controls
86 lines (74 loc) · 2.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
"""
# Definition for a Node.
class Node:
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
from collections import deque
class Solution:
def cloneGraph(self, node):
if node is None:
return None
# use bfs algorithm to traverse the graph and get all nodes.
nodes = self.getGraphNodes(node)
mapping = {}
# copy nodes, store the old->new mapping information in a hash map
for n in nodes:
mapping[n] = Node(n.val, [])
# copy neighbors(edges)
for n in nodes:
for neighbor in n.neighbors:
mapping[n].neighbors.append(mapping[neighbor]) # KEY: New edges' connection -> append(mapping[neighbor])
return mapping[node]
def getGraphNodes(self, node):
queue = deque([node]) # use list
results = [node]
while queue:
head = queue.popleft()
for neighbor in head.neighbors:
if neighbor not in results:
queue.append(neighbor)
results.append(neighbor)
return results
# LINTCODE NO.137
"""
Definition for a undirected graph node
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
"""
from collections import deque
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node is None:
return None
# use bfs algorithm to traverse the graph and get all nodes.
nodes = self.getGraphNodes(node)
# copy nodes, store the old->new mapping information in a hash map
mapping = {}
for n in nodes:
mapping[n] = UndirectedGraphNode(n.label)
# copy neighbors(edges)
for n in nodes:
for neighbor in n.neighbors:
mapping[n].neighbors.append(mapping[neighbor]) # link to the mapping dict's nodes mapping[neighbor]
return mapping[node]
def getGraphNodes(self, node):
queue = deque([node]) # use list
results = [node]
while queue:
head = queue.popleft()
for neighbor in head.neighbors:
if neighbor not in results:
queue.append(neighbor)
results.append(neighbor)
return results