-
Notifications
You must be signed in to change notification settings - Fork 1
/
CloneGraph.java
127 lines (113 loc) · 3.74 KB
/
CloneGraph.java
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
package com.hncboy;
import java.util.*;
/**
* @author hncboy
* @date 2019/11/12 15:43
* @description 133.克隆图
*
* 给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。
* 图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。
*
*
* 输入:
* {"$id":"1","neighbors":
* [{"$id":"2","neighbors":[{"$ref":"1"},
* {"$id":"3","neighbors":[{"$ref":"2"},
* {"$id":"4","neighbors":[{"$ref":"3"},
* {"$ref":"1"}],"val":4}],"val":3}],"val":2},
* {"$ref":"4"}],"val":1}
*
* 解释:
* 节点 1 的值是 1,它有两个邻居:节点 2 和 4 。
* 节点 2 的值是 2,它有两个邻居:节点 1 和 3 。
* 节点 3 的值是 3,它有两个邻居:节点 2 和 4 。
* 节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
*
* 提示:
* 节点数介于 1 到 100 之间。
* 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
* 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
* 必须将给定节点的拷贝作为对克隆图的引用返回。
*/
public class CloneGraph {
public static void main(String[] args) {
Node node1 = new Node(1, null);
Node node2 = new Node(2, null);
Node node3 = new Node(3, null);
Node node4 = new Node(4, null);
node1.neighbors = Arrays.asList(node2, node4);
node2.neighbors = Arrays.asList(node1, node3);
node3.neighbors = Arrays.asList(node2, node4);
node4.neighbors = Arrays.asList(node1, node3);
System.out.println(new CloneGraph().cloneGraph(node1));
}
/**
* DFS
*
* @param node
* @return
*/
private Node cloneGraph(Node node) {
if (node == null) {
return null;
}
return cloneGraphHelper(node, new HashMap<>());
}
private Node cloneGraphHelper(Node node, HashMap<Integer, Node> map) {
if (map.containsKey(node.val)) {
return map.get(node.val);
}
// 构造新节点
Node curr = new Node(node.val, new ArrayList<>());
map.put(curr.val, curr);
// 构造新节点的所有邻接节点
for (Node temp : node.neighbors) {
curr.neighbors.add(cloneGraphHelper(temp, map));
}
return curr;
}
/**
* BFS
*
* @param node
* @return
*/
private Node cloneGraph2(Node node) {
if (node == null) {
return null;
}
// 用于存放节点值和对应的节点
Map<Integer, Node> map = new HashMap<>();
// 构造新节点插入 map
map.put(node.val, new Node(node.val, new ArrayList<>()));
Queue<Node> queue = new LinkedList<>();
// 将第一个原始节点插入 queue
queue.add(node);
while (!queue.isEmpty()) {
Node curr = queue.poll();
// 遍历当前节点的邻接节点
for (Node temp : curr.neighbors) {
// 如果该邻接节点未在 map 中
if (!map.containsKey(temp.val)) {
// 将该节点插入 map
map.put(temp.val, new Node(temp.val, new ArrayList<>()));
// 将该节点插入 queue
queue.add(temp);
}
// 构造当前节点的邻接节点
map.get(curr.val).neighbors.add(map.get(temp.val));
}
}
return map.get(node.val);
}
private static class Node {
public int val;
List<Node> neighbors;
Node() {
}
Node(int _val, List<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
}