forked from leetcoders/LeetCode-Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCloneGraph.java
More file actions
74 lines (70 loc) · 2.81 KB
/
CloneGraph.java
File metadata and controls
74 lines (70 loc) · 2.81 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
/*
Author: Andy, nkuwjg@gmail.com
Date: Jan 13, 2015
Problem: Clone Graph
Difficulty: Medium
Source: http://oj.leetcode.com/problems/clone-graph/
Notes:
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 from 0 to N - 1, where N is the total nodes in the graph.
We use # as a separator for each node, and , as a separator for each neighbor of the node.
As an example, consider the serialized graph {1,2#2#2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
Connect node 0 to both nodes 1 and 2.
Connect node 1 to node 2.
Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
Solution: 1. DFS. 2. BFS.
*/
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
public UndirectedGraphNode cloneGraph_1(UndirectedGraphNode node) {
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
return cloneGraphRe(node, map);
}
public UndirectedGraphNode cloneGraphRe(UndirectedGraphNode node, HashMap<UndirectedGraphNode, UndirectedGraphNode> map) {
if (node == null) return null;
if (map.containsKey(node) == true) {
return map.get(node);
}
UndirectedGraphNode newnode = new UndirectedGraphNode(node.label);
map.put(node, newnode);
for (UndirectedGraphNode cur : node.neighbors) {
newnode.neighbors.add(cloneGraphRe(cur, map));
}
return newnode;
}
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
if (node == null) return null;
queue.offer(node);
map.put(node, new UndirectedGraphNode(node.label));
while (queue.isEmpty() == false) {
UndirectedGraphNode cur = queue.poll();
for (UndirectedGraphNode neighbor : cur.neighbors) {
if (map.containsKey(neighbor) == false) {
UndirectedGraphNode newnode = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, newnode);
queue.offer(neighbor);
}
map.get(cur).neighbors.add(map.get(neighbor));
}
}
return map.get(node);
}
}