forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathClone Graph.java
More file actions
executable file
·156 lines (135 loc) · 4.84 KB
/
Clone Graph.java
File metadata and controls
executable file
·156 lines (135 loc) · 4.84 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
M
1533605472
tags: DFS, BFS, Graph
给一个graph node, 每个node有list of neighbors. 复制整个graph, return new head node.
实现起来就好像在crawl urls.
#### 思想
- Use HashMap to mark cloned nodes.
- 先能复制多少Node复制多少. 然后把neighbor 加上
- Use `map<oldNode, newNode>` to mark visited
#### DFS
- Given graph node obj `{val, list of neighbor}`: copy the node and all neighbors
- Mark visited using map<oldNode, newNode>
- for loop on the each one of the neighbors: map copy, record in map, and further dfs
- once dfs completes, add newNeighbor as neighbor of the new node (get to it via map)
- 主要思想是: 一旦复制过了, 不必要重新复制
#### BFS
- Copy the root node, then copy all the neighbors.
- Mark copied node in map.
- Use queue to contain the newly added neighbors. Need to work on them in the future.
```
/*
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
/ \
\_/
Hide Tags Depth-first Search Breadth-first Search Graph
*/
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
/*
DFS
- Mark visited in map
- Add neibhors via dfs
- return node
*/
public class Solution {
// old -> node node map
Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return node;
}
if (map.containsKey(node)) {
return map.get(node);
}
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node, newNode);
for (UndirectedGraphNode neighbor: node.neighbors) {
newNode.neighbors.add(cloneGraph(neighbor));
}
return newNode;
}
}
/*
Thougths:
DFS with map in graph.
The serialized graph is just explaination for the test input.
1. copy the node
2. Mark 'added' using map(old, new)
3. for loop on the each one of the neighbors: map copy, record in map, and further dfs
4. once dfs completes, add newNeighbor as neighbor of the new node (get to it via map)
*/
public class Solution {
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
map.put(node, newNode);
dfs(node);
return newNode;
}
public void dfs(UndirectedGraphNode node) {
if (node == null) {
return;
}
for (UndirectedGraphNode neighbor: node.neighbors) {
if (!map.containsKey(neighbor)) {
UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, newNeighbor);
dfs(neighbor);
}
map.get(node).neighbors.add(map.get(neighbor));
}
}
}
/*
Thougths:
BFS, same concept as DFS.
1. Copy the root node, then copy all the neighbors.
2. Mark copied node in map.
3. Use queue to contain the neighbors for next round: if it has neighbors
*/
public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
map.put(node, new UndirectedGraphNode(node.label)); // copy root
Queue<UndirectedGraphNode> queue = new LinkedList<>();
queue.offer(node);
while(!queue.isEmpty()) {
UndirectedGraphNode curr = queue.poll();
for (UndirectedGraphNode neighbor: curr.neighbors) {
if (!map.containsKey(neighbor)) { // Init neighbors
queue.offer(neighbor);
map.put(neighbor, new UndirectedGraphNode(neighbor.label));
}
map.get(curr).neighbors.add(map.get(neighbor)); // link neighbor
}
}
return map.get(node);
}
}
```