/
Clone Graph.py
67 lines (60 loc) · 1.89 KB
/
Clone Graph.py
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
# Definition for a undirected graph node
import new
class UndirectedGraphNode:
def __init__(self, x):
self.label = x
self.neighbors = []
# depth first
class Solution:
def cloneGraph(self, node):
if node is None:
return None
start = UndirectedGraphNode(node.label)
stack = [node]
dicts = {node: start}
while stack:
current = stack.pop()
for i in current.neighbors:
if i not in dicts:
new = UndirectedGraphNode(i.label)
dicts[i] = new
stack.append(i)
dicts[current].neighbors.append(dicts[i])
return start
# breadth first
class Solution:
def cloneGraph(self, node):
if node is None:
return None
start = UndirectedGraphNode(node.label)
dicts, current = {node: start}, [node]
while current:
next = []
for i in current:
for j in i.neighbors:
if j not in dicts:
new = UndirectedGraphNode(j.label)
next.append(j)
dicts[j] = new
dicts[i].neighbors.append(dicts[j])
current = next
return start
# recursive breadth first
class Solution:
def deepcopy(self, node):
if node.label in self.hash.keys():
return self.hash[node.label]
else:
newnode = UndirectedGraphNode(node.label)
self.hash[node.label] = newnode
for i in node.neighbors:
newnode.neighbors.append(self.deepcopy(i))
return newnode
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
self.hash = {}
if node:
return self.deepcopy(node)
else:
return None