forked from shuang790228/GeekTime-MathLecture-JavaCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLesson14_2.java
More file actions
262 lines (193 loc) · 9.48 KB
/
Lesson14_2.java
File metadata and controls
262 lines (193 loc) · 9.48 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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;
import java.util.Queue;
import java.util.LinkedList;
public class Lesson14_2 {
/**
* @Description: 图的结点
*
*/
public static Random rand = new Random();
public class Node {
public int user_id; // 结点的名称，这里使用用户id
public HashSet<Integer> friends = null;
// 使用哈希映射存放相连的朋友结点。哈希便于确认和某个用户是否相连。
public int degree; // 用于存放和给定的用户结点，是几度好友
public HashMap<Integer, Integer> degrees; // 存放从不同用户出发，当前用户结点是第几度
// 初始化结点
public Node(int id) {
user_id = id;
friends = new HashSet<>();
degree = 0;
degrees = new HashMap<>();
degrees.put(id, 0);
}
}
/** 和之前一样，在讲座中可以省略
* @Description: 生成图的结点和边
* @param user_num-用户的数量，也就是结点的数量；relation_num-好友关系的数量，也就是边的数量
* @return Node[]-图的所有结点
*/
public Node[] generateGraph(int user_num, int relation_num) {
Node[] user_nodes = new Node[user_num];
// 生成所有表示用户的结点
for (int i = 0; i < user_num; i++) {
user_nodes[i] = new Node(i);
}
// 生成所有表示好友关系的边
for (int i = 0; i < relation_num; i++) {
int friend_a_id = rand.nextInt(user_num);
int friend_b_id = rand.nextInt(user_num);
if (friend_a_id == friend_b_id) continue; // 自己不能是自己的好友。如果生成的两个好友id相同，跳过
Node friend_a = user_nodes[friend_a_id];
Node friend_b = user_nodes[friend_b_id];
// 这里为了简化起见，暂时不考虑重复的好友id。如果有重复，跳过
if (!friend_a.friends.contains(friend_b_id)) {
friend_a.friends.add(friend_b_id);
}
if (!friend_b.friends.contains(friend_a_id)) {
friend_b.friends.add(friend_a_id);
}
}
return user_nodes;
}
/** 和之前一样，在讲座中可以省略
* @Description: 通过广度优先搜索，查找好友
* @param user_nodes-用户的结点；user_id-给定的用户ID，我们要为这个用户查找好友
* @return void
*/
public static void bfs(Node[] user_nodes, int user_id) {
if (user_id > user_nodes.length) return; // 防止数组越界的异常
Queue<Integer> queue = new LinkedList<Integer>(); // 用于广度优先搜索的队列
queue.offer(user_id); // 放入初始结点
HashSet<Integer> visited = new HashSet<>(); // 存放已经被访问过的结点，防止回路
visited.add(user_id);
while (!queue.isEmpty()) {
int current_user_id = queue.poll(); // 拿出队列头部的第一个结点
if (user_nodes[current_user_id] == null) continue;
// 遍历刚刚拿出的这个结点的所有直接连接结点，并加入队列尾部
for (int friend_id : user_nodes[current_user_id].friends) {
if (user_nodes[friend_id] == null) continue;
if (visited.contains(friend_id)) continue;
queue.offer(friend_id);
visited.add(friend_id); // 记录已经访问过的结点
user_nodes[friend_id].degree = user_nodes[current_user_id].degree + 1;
// 好友度数是当前结点的好友度数再加1
System.out.println(String.format("\t%d度好友：%d", user_nodes[friend_id].degree, friend_id));
}
}
}
/**
* @Description: 通过广度优先搜索，查找特定的好友
* @param user_nodes-用户的结点；user_id_a-用户a的ID；user_id_b-用户b的ID
* @return void
*/
public static void bfs(Node[] user_nodes, int user_id_a, int user_id_b) {
if (user_id_a > user_nodes.length) return; // 防止数组越界的异常
if (user_id_a == user_id_b) {
System.out.println(String.format("%d和%d两者是%d度好友", user_id_a, user_id_b, 0));
return;
}
Queue<Integer> queue = new LinkedList<Integer>(); // 用于广度优先搜索的队列
queue.offer(user_id_a); // 放入初始结点
HashSet<Integer> visited = new HashSet<>(); // 存放已经被访问过的结点，防止回路
visited.add(user_id_a);
boolean founded = false;
while (!queue.isEmpty()) {
int current_user_id = queue.poll(); // 拿出队列头部的第一个结点
if (user_nodes[current_user_id] == null) continue;
// 遍历刚刚拿出的这个结点的所有直接连接结点，并加入队列尾部
for (int friend_id : user_nodes[current_user_id].friends) {
if (user_nodes[friend_id] == null) continue;
if (visited.contains(friend_id)) continue;
queue.offer(friend_id);
visited.add(friend_id); // 记录已经访问过的结点
user_nodes[friend_id].degree = user_nodes[current_user_id].degree + 1; // 好友度数是当前结点的好友度数再加1
// 发现特定的好友，输出，然后跳出循环并返回
if (friend_id == user_id_b) {
System.out.println(String.format("%d和%d两者是%d度好友", user_id_a, user_id_b, user_nodes[friend_id].degree));
founded = true;
break;
}
}
// 已经发现特定的好友，跳出循环并返回
if (founded) break;
}
}
/**
* @Description: 通过双向广度优先搜索，查找两人之间最短通路的长度
* @param user_nodes-用户的结点；user_id_a-用户a的ID；user_id_b-用户b的ID
* @return void
*/
public static int bi_bfs(Node[] user_nodes, int user_id_a, int user_id_b) {
if (user_id_a > user_nodes.length || user_id_b > user_nodes.length) return -1; // 防止数组越界的异常
if (user_id_a == user_id_b) return 0; // 两个用户是同一人，直接返回0
Queue<Integer> queue_a = new LinkedList<Integer>(); // 队列a，用于从用户a出发的广度优先搜索
Queue<Integer> queue_b = new LinkedList<Integer>(); // 队列b，用于从用户b出发的广度优先搜索
queue_a.offer(user_id_a); // 放入初始结点
HashSet<Integer> visited_a = new HashSet<>(); // 存放已经被访问过的结点，防止回路
visited_a.add(user_id_a);
queue_b.offer(user_id_b); // 放入初始结点
HashSet<Integer> visited_b = new HashSet<>(); // 存放已经被访问过的结点，防止回路
visited_b.add(user_id_b);
int degree_a = 0, degree_b = 0, max_degree = 20; // max_degree的设置，防止两者之间不存在通路的情况
while ((degree_a + degree_b) < max_degree) {
degree_a ++;
getNextDegreeFriend(user_id_a, user_nodes, queue_a, visited_a, degree_a);
// 沿着a出发的方向，继续广度优先搜索degree + 1的好友
if (hasOverlap(visited_a, visited_b)) return (degree_a + degree_b);
// 判断到目前为止，被发现的a的好友，和被发现的b的好友，两个集合是否存在交集
degree_b ++;
getNextDegreeFriend(user_id_b, user_nodes, queue_b, visited_b, degree_b);
// 沿着b出发的方向，继续广度优先搜索degree + 1的好友
if (hasOverlap(visited_a, visited_b)) return (degree_a + degree_b);
// 判断到目前为止，被发现的a的好友，和被发现的b的好友，两个集合是否存在交集
}
return -1; // 广度优先搜索超过max_degree之后，仍然没有发现a和b的重叠，认为没有通路
}
// 广度优先搜索和user_id相距度数为degree的所有好友
public static void getNextDegreeFriend(int user_id, Node[] user_nodes, Queue<Integer> queue, HashSet<Integer> visited, int degree) {
while (!queue.isEmpty()) {
if (user_nodes[queue.peek()].degrees.get(user_id) >= degree) break;
// 首先看看，下一个从队列头部取出来的用户，他/她和出发点相距的度数是否超过了参数degree。如果超过了就跳出
int current_user_id = queue.poll(); // 拿出队列头部的第一个结点
if (user_nodes[current_user_id] == null) continue;
for (int friend_id : user_nodes[current_user_id].friends) {
if (user_nodes[friend_id] == null) continue;
if (visited.contains(friend_id)) continue;
queue.offer(friend_id);
visited.add(friend_id);
user_nodes[friend_id].degrees.put(user_id, user_nodes[current_user_id].degrees.get(user_id) + 1);
// 好友度数是当前结点的好友度数再加1
}
}
}
// 判断两个好友集合是否有交集
public static boolean hasOverlap(HashSet<Integer> friends_from_a, HashSet<Integer> friends_from_b) {
for (Integer f_a : friends_from_a) {
if (friends_from_b.contains(f_a))
return true;
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
// System.out.println(String.format("lastModifiedTime>=%d", System.currentTimeMillis() - (6*30*24*3600*1000L)));
// System.out.println(String.format("lastModifiedTime>=%d", System.currentTimeMillis()));
// System.exit(0);
Lesson14_2 l14_1 = new Lesson14_2();
Node[] user_nodes = l14_1.generateGraph(50000, 320000); //生成较大数量的结点和边，用于测试两种方法的性能差异
long start = 0, end = 0;
int a_id = 0, b_id = 1;
start = System.currentTimeMillis();
Lesson14_2.bfs(user_nodes, a_id, b_id);
end = System.currentTimeMillis();
System.out.println(String.format("耗时%d毫秒", end - start));
System.out.println();
start = System.currentTimeMillis();
System.out.println(String.format("%d和%d两者是%d度好友", a_id, b_id, Lesson14_2.bi_bfs(user_nodes, a_id, b_id)));
end = System.currentTimeMillis();
System.out.println(String.format("耗时%d毫秒", end - start));
}
}