FilesExpand file tree

 master

/

clone_graph.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

93 lines (80 loc) · 2.64 KB

 master

/

clone_graph.py

Copy path

Top

File metadata and controls

• Code
• Blame

93 lines (80 loc) · 2.64 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

87

88

89

90

91

92

93

"""

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

/ \

\_/

"""

# Definition for a undirected graph node

# class UndirectedGraphNode:

# def __init__(self, x):

# self.label = x

# self.neighbors = []

# BFS

def cloneGraph1(self, node):

if not node:

return

nodeCopy = UndirectedGraphNode(node.label)

dic = {node: nodeCopy}

queue = collections.deque([node])

while queue:

node = queue.popleft()

for neighbor in node.neighbors:

if neighbor not in dic: # neighbor is not visited

neighborCopy = UndirectedGraphNode(neighbor.label)

dic[neighbor] = neighborCopy

dic[node].neighbors.append(neighborCopy)

queue.append(neighbor)

else:

dic[node].neighbors.append(dic[neighbor])

return nodeCopy

# DFS iteratively

def cloneGraph2(self, node):

if not node:

return

nodeCopy = UndirectedGraphNode(node.label)

dic = {node: nodeCopy}

stack = [node]

while stack:

node = stack.pop()

for neighbor in node.neighbors:

if neighbor not in dic:

neighborCopy = UndirectedGraphNode(neighbor.label)

dic[neighbor] = neighborCopy

dic[node].neighbors.append(neighborCopy)

stack.append(neighbor)

else:

dic[node].neighbors.append(dic[neighbor])

return nodeCopy

# DFS recursively

def cloneGraph(self, node):

if not node:

return

nodeCopy = UndirectedGraphNode(node.label)

dic = {node: nodeCopy}

self.dfs(node, dic)

return nodeCopy

def dfs(self, node, dic):

for neighbor in node.neighbors:

if neighbor not in dic:

neighborCopy = UndirectedGraphNode(neighbor.label)

dic[neighbor] = neighborCopy

dic[node].neighbors.append(neighborCopy)

self.dfs(neighbor, dic)

else:

dic[node].neighbors.append(dic[neighbor])