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

精选留言(14)

• 

  elephant

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

  作者回复: 是的

  2019-01-19

  

   16
• 

  菩提

  完善了一下这两个预留的方法
  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
  
  老师您帮忙看下程序逻辑有没有什么问题，从测试结果来看应该是对的。

  作者回复: 逻辑上是对的👌

  2019-01-16

  

   5
• 

  Wing·三金

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

  作者回复: 思考题的思路很好。
  degree_a和degree_b主要是控制总的度数（也就是max_degree），不要搜索太多。
  
  至于HashMap，是考虑到了不同节点到出发点的最短距离。

  2019-03-25

  

   1
• 

  风轨

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

  作者回复: 考虑到了网络的动态改变，这个思路很赞👍

  2019-01-30

  

   1
• 

  一页遮目

  要想实现双向广度优先搜索，首先我们要把结点类 Node 稍作修改，增加一个变量 degrees。这个变量是 HashSet 类型。
  老师上面应该讲错了，degrees是HashMap类型

  作者回复: 感谢指正

  2019-12-05

  

  
• 

  teddytyy

  度数小的情况，单向广度优先更有效

  作者回复: 是的

  2019-12-05

  

  
• 

  Geek_zy

  感觉单向可以看作O(n^2)指数级别的增长 双向的更趋近于O(2*n)的增长

  作者回复: 从数量级来看是相同的，但是实际差别还是很大

  2019-10-24

  

  
• 

  qinggeouye

  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

  作者回复: 思路是对的，使用set实现代码也很简洁

  2019-02-25

  

  
• 

  Joe

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

  作者回复: 计算“公司”那一层是，一开始还是需要100 * 5个计数器，之后才会取前1个，也就是100*1。对于“同事”那一层同理

  2019-01-23

  

  
• 

  🌞🇨🇳👦

  文中描述交替看两边是否有交集的段落，b,b{1}是否出现在a,a{1},a{2}，是不是没有必要呢，因为前面已经判断了a,a{1}不在b,b{1}的并集中，是不是只需判断b,b{1}是否出现在a{2}即可

  作者回复: 很好的观察👍 这样确实可以在实现的时候进行优化

  2019-01-22

  

  
• 

  蒋宏伟

  代码布局有些错乱

  作者回复: 后面会整理代码的Github，供大家参考

  2019-01-21

  

  
• 

  永旭

  老师 ,在哪里能看 getNextDegreeFriend 和 hasOverlap 的代码 ?

  作者回复: 因为篇幅的关系，原文没有给出，我会在第一大部分结束后，整理一个GitHub。请关注加餐栏目，到时会给出链接。

  2019-01-15

  

  
• 

  Being

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

  作者回复: 是的，规模小不能体现双向优势。另外，如果两个出发点a和b，如果a出发的图平均连接度明显大于b出发的图，那么从b单向广度可能效率更高。

  2019-01-15

  

  
• 

  草原上的奔跑

  双向广度优先搜索应该是两个点要联通吧，感觉这是一个前提条件。图论这块内容，已经触及到我的盲区了，但是建立在这之上的内容很重要，深度搜索和广度搜索都是向一个资深程序员迈进要走的路。虽然走的时候很痛苦，但依然坚持，我喜欢看到路尽头的彩虹。

  作者回复: 对，前提要连通，否则就无解了。编码的时候可以加个判断，路径长度是否已经超出一个的阈值，或者是否有新的结点发现，可以防止代码在两者不连通的情况下，陷入死循环。

  2019-01-15

  

  