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.
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
2
3
4
5
6
| 1
/ \
/ \
0 --- 2
/ \
\_/
|
Solution
Java
DFS
(Clone-Graph.java) download
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
| /**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
// 已经创建过的node,label 映射<label, Node>
private HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return clone(node);
}
public UndirectedGraphNode clone(UndirectedGraphNode node){
if(node==null) return null;
if(map.containsKey(node.label)) return map.get(node.label);
// 不在map中，说明之前没有给这个节点创建object.
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node.label, newNode);
// copy neighbors
for(UndirectedGraphNode neighbor : node.neighbors){
newNode.neighbors.add(clone(neighbor));
}
return newNode;
}
}
|
Python
(Clone-Graph.py) download
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
| # Definition for a undirected graph node
# class UndirectedGraphNode(object):
# def __init__(self, x):
# self.label = x
# self.neighbors = []
# Definition for a undirected graph node
# class UndirectedGraphNode(object):
# def __init__(self, x):
# self.label = x
# self.neighbors = []
class Solution(object):
def __init__(self):
# hash_map{label:new_node}
self.hash_map = {}
def cloneGraph(self, node):
"""
:type node: UndirectedGraphNode
:rtype: UndirectedGraphNode
"""
# hash_map: {new_node:new_node.label)
if node == None:
return None
if node.label in self.hash_map:
return self.hash_map[node.label]
# new node
root = UndirectedGraphNode(node.label)
# update hash_map
self.hash_map[node.label] = root
for neighbor in node.neighbors:
root.neighbors.append(self.cloneGraph(neighbor))
return root
|