极客时间已完结课程限时免费阅读

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

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

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

2019-01-14 黄申 来自北京
《程序员的数学基础课》
课程介绍

讲述：黄申

时长13:20大小12.20M

你好，我是黄申。
上一讲，我们通过社交好友的关系，介绍了为什么需要广度优先策略，以及如何通过队列来实现它。有了广度优先搜索，我们就可以知道某个用户的一度、二度、三度等好友是谁。不过，在社交网络中，还有一个经常碰到的问题，那就是给定两个用户，如何确定他们之间的关系有多紧密？
最直接的方法是，使用这两人是几度好友，来衡量他们关系的紧密程度。今天，我就这个问题，来聊聊广度优先策略的一种扩展：双向广度优先搜索，以及这种策略在工程中的应用。

如何更高效地求出两个用户间的最短路径？

基本的做法是，从其中一个人出发，进行广度优先搜索，看看另一个人是否在其中。如果不幸的话，两个人相距六度，那么即使是广度优先搜索，同样要达到万亿级的数量。
那究竟该如何更高效地求得两个用户的最短路径呢？我们先看看，影响效率的问题在哪里？很显然，随着社会关系的度数增加，好友数量是呈指数级增长的。所以，如果我们可以控制这种指数级的增长，那么就可以控制潜在好友的数量，达到提升效率的目的。
如何控制这种增长呢？我这里介绍一种“双向广度优先搜索”。它巧妙地运用了两个方向的广度优先搜索，大幅降低了搜索的度数。现在我就带你看下，这个方法的核心思想。
假设有两个人 、。
我们首先从 出发，进行广度优先搜索，记录 的所有一度好友 ，然后看点 是否出现在集合 中。
如果没有，就再从 出发，进行广度优先搜索，记录所有一度好友 ，然后看 和 是否出现在 和 的并集中。
如果没有，就回到 ，继续从它出发的广度优先搜索，记录所有二度好友 ，然后看 和 是否出现在 、 和 三者的并集中。
如果没有，就回到 ，继续从它出发的广度优先搜索。
如此轮流下去，直到找到 的好友和 的好友的交集。
如果有交集，就表明这个交集里的点到 和 都是通路。
我们假设 在这个交集中，那么把 到 的通路长度和 到 的通路长度相加，得到的就是从 到 的最短通路长（这个命题可以用反证法证明），也就是两者为几度好友。这个过程有点复杂，我画了一张图帮助你来理解。
思路你应该都清楚了，现在我们来看看如何用代码来实现。
要想实现双向广度优先搜索，首先我们要把结点类 Node 稍作修改，增加一个变量 degrees。这个变量是 HashMap 类型，用于存放从不同用户出发，到当前用户是第几度结点。比如说，当前结点是 4，从结点 1 到结点 4 是 3 度，结点 2 到结点 4 是 2 度，结点 3 到结点 4 是 4 度，那么结点 4 的 degrees 变量存放的就是如下映射：
有了变量 degrees，我们就能随时知道某个点和两个出发点各自相距多少。所以，在发现交集之后，根据交集中的点和两个出发点各自相距多少，就能很快地算出最短通路的长度。理解了这点之后，我们在原有的 Node 结点内增加 degrees 变量的定义和初始化。
public class Node {
......
public HashMap<Integer, Integer> degrees; // 存放从不同用户出发，当前用户结点是第几度
// 初始化结点
public Node(int id) {
......
degrees = new HashMap<>();
degrees.put(id, 0);
}
}
为了让双向广度优先搜索的代码可读性更好，我们可以先实现两个模块化的函数：getNextDegreeFriend 和 hasOverlap。函数 getNextDegreeFriend 是根据给定的队列，查找和起始点相距度数为指定值的所有好友。而函数 hasOverlap 用来判断两个集合是不是有交集。有了这些模块化的函数，双向广度优先搜索的代码就更直观了。
在函数一开始，我们先进行边界条件判断。
/**
* @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
由于同时从两个用户的结点出发，对于所有，有两条搜索的路径，我们都需要初始化两个用于广度优先搜索的队列，以及两个用于存放已经被访问结点的 HashSet。
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的重叠，认为没有通路
}
你可以同时实现单向广度优先搜索和双向广度优先搜索，然后通过实验来比较两者的执行时间，看看哪个更短。如果实验的数据量足够大（比如说结点在 1 万以上，边在 5 万以上），你应该能发现，双向的方法对时间和内存的消耗都更少。
为什么双向搜索的效率更高呢？我以平均好友度数为 4，给你举例讲解。
左边的图表示从结点 单向搜索走 2 步，右边的图表示分别从结点 和 双向搜索各走 1 步。很明显，左边的结点有 16 个，明显多于右边的 8 个结点。而且，随着每人认识的好友数、搜索路径的增加，这种差距会更加明显。
我们假设每个地球人平均认识 100 个人，如果两个人相距六度，单向广度优先搜索要遍历 100^6=1 万亿左右的人。如果是双向广度优先搜索，那么两边各自搜索的人只有 100^3=100 万。
当然，你可能会说，单向广度优先搜索之后查找匹配用户的开销更小啊。的确如此，假设我们要知道结点 和 之间的最短路径，单向搜索意味着要在 的 1 万亿个好友中查找 。如果采用双向搜索的策略，从结点 和 出发进行广度优先搜索，每个方向会产生 100 万的好友，那么需要比较这两组 100 万的好友是否有交集。
假设我们使用哈希表来存储 的 1 万亿个好友，并把搜索 是否存在其中的耗时记作 x，而把判断两组 100 万好友是否有交集的耗时记为 y，那么通常 x<y。
不过，综合考虑广度优先搜索出来的好友数量，双向广度优先搜索还是更有效。为什么这么说呢？稍后介绍算法复杂度的概念和衡量方法时，我会具体来分析这个例子。
广度优先搜索的应用场景有很多，下面我来说说这种策略的一个应用。

如何实现更有效地嵌套型聚合？

广度优先策略可以帮助我们大幅优化数据分析中的聚合操作。聚合是数据分析中一个很常见的操作，它会根据一定的条件把记录聚集成不同的分组，以便我们统计每个分组里的信息。目前，SQL 语言中的 GROUP BY 语句，Python 和 Spark 语言中 data frame 的 groupby 函数，Solr 的 facet 查询和 ElasticSearch 的 aggregation 查询，都可以实现聚合的功能。
我们可以嵌套使用不同的聚合，获得层级型的统计结果。但是，实际上，针对一个规模超大的数据集，聚合的嵌套可能会导致性能严重下降。这里我来谈谈如何利用广度优先的策略，对这个问题进行优化。
首先，我用一个具体的例子来给你讲讲，什么是多级嵌套的聚合，以及为什么它会产生严重的性能问题。
这里我列举了一个数据表，它描述了一个社交网络中，每个人的职业经历。字段包括项目的 ID、用户 ID、公司 ID 和同事的 IDs。
对于这张表，我们可以进行三层嵌套的聚集。第一级是根据用户 ID 来聚，获取每位用户一共参与了多少项目。第二级是根据公司 ID 来聚，获取每位用户在每家公司参与了多少项目。第三级根据同事 ID 来聚，获取每位用户在每家公司，和每位同事共同参与了多少项目。最终结果应该是类似下面这样的：
用户u88，总共50个项目（包括在公司c42中的10个，c26中的8个...）
在公司c42中，参与10个项目（包括和u120共事的4个，和u99共事的3个...）
和u120共同参与4个项目
和u99共同参与3个项目
和u72共同参与3个项目
在公司c26中，参与了8个项目
和u145共同参与5个项目
和u128共同参与3个项目
（用户u88在其他公司的项目...）
用户u66，总共47个项目
在公司c28中，参与了16个项目
和u65共同参与了5个项目
(用户u66的剩余数据...）
...
（其他用户的数据...）
为了实现这种嵌套式的聚合统计，你会怎么来设计呢？看起来挺复杂的，其实我们可以用最简单的排列的思想，分别为“每个用户”“每个用户 + 每个公司”“每个用户 + 每个公司 + 每位同事”，生成很多很多的计数器。可是，如果用户的数量非常大，那么这个“很多”就会成为一个可怕的数字。
我们假设这个社交网有 5 万用户，每位用户平均在 5 家公司工作过，而用户在每家公司平均有 10 名共事的同事，那么针对用户的计数器有 5 万个，针对“每个用户 + 每个公司”的计数器有 25 万个，而到了“每个用户 + 每个公司 + 每位同事”的计数器，就已经达到 250 万个了，三个层级总共需要 280 万计数器。
我们假设一个计数器是 4 个字节，那么 280 万个计数器就需要消耗超过 10M 的内存。对于高并发、低延迟的实时性服务，如果每个请求都要消耗 10M 内存，很容易就导致服务器崩溃。另外，实时性的服务，往往只需要前若干个结果就足以满足需求了。在这种情况下，完全基于排列的设计就有优化的空间了。
从刚才那张图中，其实我们就能想到一些优化的思路。
对于只需要返回前若干结果的应用场景，我们可以对图中的树状结构进行剪枝，去掉绝大部分不需要的结点和边，这样就能节省大量的内存和 CPU 计算。
比如，如果我们只需要返回前 100 个参与项目最多的用户，那么就没有必要按照深度优先的策略，去扩展树中高度为 2 和 3 的结点了，而是应该使用广度优先策略，首先找出所有高度为 1 的结点，根据项目数量进行排序，然后只取出前 100 个，把计数器的数量从 5 万个一下子降到 100 个。
以此类推，我们还可以控制高度为 2 和 3 的结点之数量。如果我们只要看前 100 位用户，每位用户只看排名第一的公司，而每家公司只看合作最多的 3 名同事，那么最终计数器数量就只有 50000+100x5+100x1x10=51500。只有文字还是不太好懂，我画了一张图，帮你理解这个过程。
如果一个项目用到排列组合的思想，我们需要在程序里使用大量的变量，来保存数据或者进行计算，这会导致内存和 CPU 使用量的急剧增加。在允许的情况下，我们可以考虑使用广度优先策略，对排列组合所生成的树进行优化。这样，我们就可以有效地缩减树中靠近根的结点数量，避免之后树的爆炸性生长。

小结

广度优先搜索，相对于深度优先搜索，没有函数的嵌套调用和回溯操作，所以运行速度比较快。但是，随着搜索过程的进行，广度优先需要在队列中存放新遇到的所有结点，因此占用的存储空间通常比深度优先搜索多。
相比之下，深度优先搜索法只保留用于回溯的结点，而扩展完的结点会从栈中弹出并被删除。所以深度优先搜索占用空间相对较少。不过，深度优先搜索的速度比较慢，而并不适合查找结点之间的最短路径这类的应用。

思考题

今天所说的双向广度优先比单向广度优先更高效，其实是要基于一个前提条件的。你能否说出，在什么情况下，单向广度优先更高效呢？针对这种情况，又该如何优化双向广度优先呢？
欢迎在留言区交作业，并写下你今天的学习笔记。你可以点击“请朋友读”，把今天的内容分享给你的好友，和他一起精进。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 6

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
13 | 树的广度优先搜索（上）：人际关系的六度理论是真的吗？
下一篇
15 | 从树到图：如何让计算机学会看地图？
unpreview
 写留言

精选留言(27)

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

    作者回复: 是的

    40
  • 菩提
    2019-01-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 老师您帮忙看下程序逻辑有没有什么问题，从测试结果来看应该是对的。
    展开

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

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

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

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

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

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

    作者回复: 交替扩展是好思路

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

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

    共 2 条评论
    4
  • 罗耀龙@坐忘
    2020-04-06
    茶艺师学编程 今天说到的双向广度优先搜索，其中的思想在信息论中也有应用，就是正交信息，其大体意思为 用不同纬度的信息能很好地消除不确定性，如果信息是正交的，效果最好。 这好比如，在医院看病，医生一般会请你做血项检验和医学影像扫描，这两组不同纬度的信息（检查结果）组合起来用，医生对你身体出了什么问题有整体的把握（虽然这被大家诟病为“乱检查”）。但如果一个医生开出了CT扫描+核磁共振，大家都是同一纬度的，前面的CT扫描就等于白做了。 而这样的思想，其实我们还在学生时代就已经实践过了，那就是考试前老师一再重复强调的，“检查题目的时候，要换个思路（方法）来。” 考试的题目肯定存在不同的解法。但是任意的集合A和集合B有没有交集，交集大不大，在一开始的时候是不清楚的，因此在这时候就使用双向广度优先搜索，我觉得这大神心里是有把握的，他对将要处理数据有大体的认识。
    展开
    2
  • escray
    2020-02-03
    深度优先搜索占用空间少，但是速度比较慢；广度优先搜索占用空间多，但是运行速度快，属于空间换时间吧。进一步，双向广度优先搜索，似乎也是用了更多的空间，来换取搜索效率。 对于后来那个聚类的例子，我有点不理解，感觉更多的时采用了剪枝的思路，和双向广度优先搜索好像没什么关系，当然也可以说是把之前的深度优先搜索，改为了广度优先同时剪枝。 对于思考题，在需要列举全部好友关系的情况下，以及在树的分叉比较多的情况下，似乎单向广度优先搜索的效率更高，主要是因为减少了比对的复杂性。 看了一下回复里面的答案，说是在 a 和 b 好友分布不均匀的情况下，从好友少的一段开始单向广度搜索，效果更好。 学习了 @菩提 的 Java 代码 和 @qinggeouye 的 Python 代码
    展开
    1
  • escray
    2020-01-08
    不好意思，把 12 课的留言贴到 14 课这里了，请老师忽略
    1
  • 建强
    2020-01-05
    思考题：个人理解，当待查的两个结点相距较远，且各自都有大量好友时，则每往前搜索一步，判断两者好友的交集效率会非常低，即hasOverlap函数的效率会非常低。改进的方法，是否可考虑共用一个visited表，可以采用hash表存贮，存贮好友结点时，连同源节点的标识符（即待查的两个结点）一起存入，当发现结点存贮有冲突，且冲突的两个结点的源结点标识符不一致，则说明发现了两个待查结点的共同好友。 以上是个人一点肤浅理解，请老师指正。
    展开

    作者回复: 这个想法很好，确实可行👍

    1
  • qinggeouye
    2019-02-25
    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实现代码也很简洁

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

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

    共 2 条评论
    1
  • 蒋宏伟
    2019-01-21
    代码布局有些错乱

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

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

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

    1
  • 杨芸芸
    2023-01-02 来自湖北
    双向搜索的代码demo有bug，degree_a和degree_b最大相差1，实际中不一定的; 比如a-b-g-h、e-c-k-b-g-h,a、e的好友度demo计算结果是8但实际是4。应该从交集node中选择degree和最小的的作为结果。 双向广度优先比单向广度优先更高效：a、b的a和b好友分布极不均匀，a的子节点很多，b的子节点很少，从b开始的单向搜索会更高效
    展开
  • Leon Wong
    2022-11-29 来自广东
    BFS 遍历可以剪枝的前提应该是业务需求决定的，不是技术决定的。
  • Leon Wong
    2022-11-29 来自广东
    稍微捋一捋剪枝过程： 1、先遍历5w个用户 L1 节点； （+50000） 2、排序+剪枝，5w个取100个L1节点； 3、BFS遍历 100 L1节点的后辈节点 100 x 5个 L2节点；（+500） 4、 排序+剪枝，每个L1节点只保留一个权数最高的后辈L2节点，共保留100个 L3节点； 5、BFS遍历 100 L3节点的后辈节点 100 x 10个 L4节点；（+1000） 6、排序+剪枝，每个L3节点只保留3个权数最高的后辈L4节点。 那么，如上流程，一共遍历了 50000+500+1000 = 51500 个节点
    展开
  • 013923
    2022-07-28 来自陕西
    谢谢！
  • 凹凸鸿
    2020-12-18
    老师，上亿级别数据的项目数据库要怎么设计？怎么做到查询最优，现在一个400万数据的表查询花了30秒

    作者回复: 个人觉得哈希、缓存、数据库索引等基本技术都是可以考虑的。另外，我们还需要考虑应用和数据的特性，看看哪种技术才或者哪些技术的结合，才是最适合的

  • 凹凸鸿
    2020-12-11
    比如说，当前结点是 4，从结点 1 到结点 4 是 3 度，结点 2 到结点 4 是 2 度，结点 3 到结点 4 是 4 度---节点3到节点4为什么是4度？

    作者回复: 这里只是举一个例子，并非和前图对应