14 | 树的广度优先搜索（下）：为什么双向广度优先搜索的效率更高？

如果a和b好友分布极不均匀，比如a和a的所有子好友平均都有100个好友，b和b的所有子好友平均有2个好友，这样的情况下，从b开始的单向搜索要高效很多吧

完善了一下这两个预留的方法 private static boolean hasOverlap(HashSet<Integer> visited_a, HashSet<Integer> visited_b) { if (visited_a.isEmpty() || visited_b.isEmpty()) return false; for (int user_id_a : visited_a) { if (visited_b.contains(user_id_a)) { return true; } } return false; } private static void getNextDegreeFriend(int user_id_a, Node[] user_nodes, Queue<Integer> queue_a, HashSet<Integer> visited_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 (int f_user_id : friends) { queue_a.offer(f_user_id); visited_a.add(f_user_id); degrees.put(f_user_id, degree_a + 1); } } // 初始化节点数组 public static Node[] init(int user_num, int relation_num) { Random rand = new Random(); 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; Node friend_a = user_nodes[friend_a_id]; Node friend_b = user_nodes[friend_b_id]; friend_a.friends.add(friend_b_id); friend_b.friends.add(friend_a_id); } return user_nodes; } // 测试 public static void main(String[] args) { Node[] user_nodes = init(5, 8); for (Node d : user_nodes) { System.out.println(d.user_id + ":" + d.friends + ":" + d.degrees); } System.out.println("-----------------"); int len = bi_bfs(user_nodes, 0, 1); System.out.println("距离：" + len); } 运行结果： 0:[2, 3, 4]:{0=0} 1:[2, 4]:{1=0} 2:[0, 1]:{2=0} 3:[0]:{3=0} 4:[0, 1]:{4=0} ----------------- 距离：2 老师您帮忙看下程序逻辑有没有什么问题，从测试结果来看应该是对的。

老师，我理解的双向广度优先搜索，其实重点关注的是两个点之间的联系（最短距离），而不是中间所有的覆盖关系。单向的必然导致大规模的覆盖搜索，像地毯式的，而双向的，不会把面积铺得那么大，在一定范围内找到交集即达到目的。所以也从侧面印证了，当关系网的规模很大的时候，使用双向的搜索覆盖面积必然比单向的小很多，而规模小反而不能体现双向BFS的优势。

思考题：能想到的是当 a b 结点的好友数量极度不对称时，单向更快；优化思路是，每一次迭代时比较下一层结点的数量，若是两边的数量级有明显差距（设置个阈值），则优先选择数量级小的一边进行搜索。但这样的做的弊端也很明显——很可能这一边不断往下搜索，但事实上另一边只要往下一层就完事了。所以还需要限制单边【连续优先搜索】的次数。 提问：老师，您有开头提到需要对 Node 添加一个 degrees 的 HashMap 变量来纪录其他用户结点与 self 的距离，但是后边用到的外部变量 degree_a 事实上就代替了这个功能是吗？ 另外在实际应用中 max_degree 是设置为树的高度吗，还是可以有其他优化方式？

两边平均节点度不均匀时，从节点度小的方向单向查找效率较高。此时如果优化，可以用两边发现的好友数控制，当a的好友数大于b的，把b的好友向外扩展一度，否则扩展a的。这样交替扩展，应该能提高效率

"双向广度优先比单向广度优先更高效"的前提条件是"两个被搜索的节点必须是联通的"如果不是联通的，两个节点都会将他们各自的N度好友都找出来，不如只搜索其中一个； 针对这种情况可以维护一个网络分块信息表，每当有连接加入这个网络时检查一下它是否将两个分割的块连接起来了，如果是将这两个块标记为同一个块。在查找的时候就方便了，如果两个节点本身就不在一个块里面，距离直接就是无穷远。但是如果这个网络里面的连接还能删除的话就比较麻烦了，每删除一条边还要检查是否将一个块分割成了两个块，计算量比较大。

思考题：个人理解，当待查的两个结点相距较远，且各自都有大量好友时，则每往前搜索一步，判断两者好友的交集效率会非常低，即hasOverlap函数的效率会非常低。改进的方法，是否可考虑共用一个visited表，可以采用hash表存贮，存贮好友结点时，连同源节点的标识符（即待查的两个结点）一起存入，当发现结点存贮有冲突，且冲突的两个结点的源结点标识符不一致，则说明发现了两个待查结点的共同好友。 以上是个人一点肤浅理解，请老师指正。

https://github.com/qinggeouye/GeekTime/blob/master/MathematicProgrammer/14_breadthFirstSearch/lesson14_1.py 两个预留方法的 python 实现： get_next_degree_friend(user_nodes, que, visited) 去掉了 user_id_a 和 degree_a 两个参数。 如果把 user_id_a 看作圆心，它的一度好友看作第一层节点，二度好友看作第二层节点 .... ，que 队列只保留某一层的节点即可，visited 仍保存所有访问过的节点。 def get_next_degree_friend(user_nodes, que, visited): """ :param user_nodes: 用户节点网络 :param que: 某一层用户节点 即第几度好友 :param visited: 已访问的所有用户节点 :return: """ que_return = queue.Queue() # 只保存某个用户的第几度好友 visited_return = set() # 保存从某个用户开始到第几度好友 while not que.empty(): current_user_id = que.get() if user_nodes[current_user_id] is None: continue for friend_id in user_nodes[current_user_id].friends: if user_nodes[friend_id] is None: continue if friend_id in visited: continue que_return.put(friend_id) visited_return.add(friend_id) # 记录已经访问过的节点 return que_return, visited_return def has_overlap(visited_a, visited_b): # 两个 set() 的交集 return len(visited_a & visited_b) > 0 #测试结果： if __name__ == "__main__": user_nodes_list = set_user_relation(10, 20) for i in range(len(user_nodes_list)): print("用户 %s 的好友: %s" % (user_nodes_list[i].user_id, user_nodes_list[i].friends)) print("---------双向广度优先搜索---------") print("两个用户节点 1和2 之间的最短路径长度：", bi_bfs(user_nodes_list, 1, 2)) 用户 0 的好友: {8, 2, 3, 6} 用户 1 的好友: {8, 3, 5} 用户 2 的好友: {0, 4} 用户 3 的好友: {0, 1, 4, 5, 8, 9} 用户 4 的好友: {2, 3} 用户 5 的好友: {9, 3, 6, 1} 用户 6 的好友: {0, 8, 5} 用户 7 的好友: {9} 用户 8 的好友: {0, 1, 3, 6, 9} 用户 9 的好友: {8, 3, 5, 7} ---------双向广度优先搜索--------- 两个用户节点 1和2 之间的最短路径长度： 3

最后一个图没有看明白，图和计算结果对不上吧。不应该是5000+100+100+300吧

代码布局有些错乱