algorithms-1/graph/clone_graph.py at master · githubch/algorithms-1 · GitHub

History

93 lines (80 loc) · 2.64 KB

Raw

"""

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:

/ \

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])

algorithms-1/graph/clone_graph.py at master · githubch/algorithms-1 · GitHub

Expand file tree

Breadcrumbs

clone_graph.py

Latest commit

History

Breadcrumbs

clone_graph.py

File metadata and controls