https://kyrenesjtv.github.io/
/**
* 双向广度查找两个用户之间的广度距离
* @param user_nodes 好友关系网
* @param user_id_a 用户a的ID
* @param user_id_b 用户b的ID
* @return 用户a b 的广度距离 -1表示超出距离或者没有找到，0表示a和b是相同用户
*/
public static int bi_bfs(Node[] user_nodes , int user_id_a , int user_id_b){
//用户id超出关系网长度
if(user_id_a > user_nodes.length || user_id_b>user_nodes.length){
return -1;
}
//用户相同
if(user_id_a == user_id_b){
return 0;
}
//队列a
LinkedList<Integer> quene_a = new LinkedList<>();
//队列b
LinkedList<Integer> quene_b = new LinkedList<>();
//a放入队列
quene_a.offer(user_id_a);
//a 访问过的人
HashSet<Integer> set_a = new HashSet<>();
set_a.add(user_id_a);
//b放入队列
quene_b.offer(user_id_b);
//b 访问过的人
HashSet<Integer> set_b = new HashSet<>();
set_b.add(user_id_b);
//max_degree 防止死循环
int degree_a = 0 ,degree_b = 0 ,max_degree =20;
while((degree_a +degree_b) <max_degree){
degree_a++;
//沿着a的方向，继续广度朝赵degree +1 的好友
getNextDegreeeFriend(user_id_a,user_nodes,quene_a,set_a,degree_a);
//判断是否有交集
if(hasOverlap(set_a,set_b)){
return degree_a +degree_b;
}
degree_b++;
//沿着a的方向，继续广度朝赵degree +1 的好友
getNextDegreeeFriend(user_id_b,user_nodes,quene_b,set_b,degree_b);
//判断是否有交集
if(hasOverlap(set_a,set_b)){
return degree_a +degree_b;
}
}
return -1 ;
}
/**
* 判断2个hashSet是否有交集
* @param set_a
* @param set_b
* @return true有交集， false没有
*/
private static boolean hasOverlap(HashSet<Integer> set_a, HashSet<Integer> set_b) {
if(set_a.isEmpty() || set_b.isEmpty()){
return false;
}
for (Integer num : set_a){
if(set_b.contains(num)){
return true;
}
}
return false;
}
/**
* 找到当前用户的下一度好友
* @param user_id_a 当前用户的id
* @param user_nodes 人际关系网
* @param quene_a 队列，将要被查找的人的id
* @param set_a 已被探测到跟a有关系的人
* @param degree_a 几度好友
*/
private static void getNextDegreeeFriend(int user_id_a, Node[] user_nodes, LinkedList<Integer> quene_a, HashSet<Integer> set_a, int degree_a) {
if(user_nodes[user_id_a] == null){
return;
}
Node current_node = user_nodes[user_id_a];
//获取到当前用户的好友
HashSet<Integer> friends = current_node.friends;
if(friends.isEmpty()){
return;
}
HashMap<Integer, Integer> degrees = current_node.degrees;
//填充数据
for(Integer frindID : friends){
quene_a.offer(frindID);
set_a.add(frindID);
degrees.put(frindID,degree_a);
}
}