31 | 深度和广度优先搜索：如何找出社交网络中的三度好友关系？
该思维导图由 AI 生成，仅供参考
什么是“搜索”算法？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了深度优先搜索和广度优先搜索算法在社交网络中寻找三度好友关系的应用。首先解释了搜索算法在图数据结构上的应用，以及图的存储方法。详细介绍了广度优先搜索算法的原理和代码实现，包括时间、空间复杂度的分析。广度优先搜索算法通过“地毯式”层层推进的搜索策略，能够找出最短路径。文章总结了广度优先搜索的时间复杂度为O(V+E)，空间复杂度为O(V)。接着介绍了深度优先搜索算法的原理和代码实现，以及其时间、空间复杂度。然后讨论了如何在社交网络中利用广度优先搜索算法找出三度好友关系。总结指出，广度优先搜索和深度优先搜索是图上最基本的搜索算法，适用于状态空间不大的搜索。广度优先搜索需要借助队列来实现，而深度优先搜索则适合用递归实现。最后，提出了课后思考问题，鼓励读者思考如何用深度优先搜索解决问题，以及如何将迷宫抽象成图并在计算机中存储。整体而言，本文通过简洁清晰的语言，帮助读者快速了解了深度优先搜索和广度优先搜索算法在社交网络中的应用，以及它们的原理和实现方式。
《数据结构与算法之美》，新⼈⾸单¥68
全部留言(187)
- 最新
- 精选
Jerry银银朗读者原谅我的有强迫症：queue这个单词读错了，付上正确的音标如下［kju］ 我觉得避免这种问题，有个方法就是，朗读之前，逐个查询一下单词的正确发音，一篇文章中的单词屈指可数，这个工作量按理说应该不大。 但是这个简单的举措，能大大提高听文章的体验，不然听起来总觉得很怪 往大了说影响，毕竟咱们极客时间做的是知识，做的是学问作者回复: 😂
2018-12-0330264
李东勇老师， 我觉得深度优先搜索的代码中有一个可以改进的地方， 可以在21行之后加一句： if (found == true) return; 这样， 在一个顶点的for循环之中， 如果已经找到了t, 就可以跳出这个for循环了。目前的逻辑是， 这个for循环中剩下的还会继续执行， 每次都调用一次recurDfs函数， 但recurDfs函数在第一行就return了。作者回复: 嗯嗯 👍
2018-12-18663
luo老师针对图这个数据结构的应用 我有点疑惑，从结构来看无论是临近矩阵还是临近表 其实都需要有一个唯一下标作为这个顶点，那么问题来了 在实际数据量庞大的时候，这种数据结构是不是就没法用了（临近矩阵就不说了，临近表的话也是需要一个大的数组存储每个顶点 ），或者只能拆成以hash先分id，之后映射到对应的机器上存储各自的临近表部分，但这样进行深度广度搜索就有网络io了。作者回复: 你说的没错，但是做工程就是trade-off，只能权衡来选择方案。如果实在存不下，可以降低些执行效率。不过，现在有很多图数据库，也可以解决你说的问题，把图直接存在硬盘中。
2019-01-0418
Liam对于今天的问题，无权图，如果采用深度优先。拿到的路径不一定是最短路径吧作者回复: 不是最短路径的。广度优先可以取到最短路径。
2019-02-13214
-W.LI-弱弱的问一句，prev和visited用数组存是正好value和下标一致才行的吧?作者回复: 是的
2019-10-2037- possible广度优先用的queue（先进先出），深度优先把queue换成stack（后进先出）即可吧？也经常会用stack来替代递归
作者回复: 是的
2019-04-287 - JzyCc弱弱的问一下，宽搜代码那块，如果给的图中 1 和 3的位置互换，那么得出来的就不是最短路径了吧
作者回复: 不，宽搜对于无权图来说，肯定能找到最短路径的。因为整体的逻辑是离起点越近的，越早被访问到。
2019-02-096 
他在她城断了弦可不可以这样理解，深度优先用递归思想，广度优先用迭代思想？作者回复: 不大行 因为深度优先也可以用非递归的方式实现
2018-12-0424- gesanri没明白文中说的广度优先遍历是起始顶点到终止顶点的最短路径是什么意思？就举的这个例子来说，按照广度优先的算法，一直到倒数第二个顶点才扫描到终止节点，总共经历了七个顶点，而肉眼上看明显有更短的路径，比如0346，只经历了四个顶点
作者回复: 路径的意思你理解错了 你可以看下prev数组
2018-12-083 
Smallfly老师把广度和深度优先搜索讲的真的是通俗易懂。我有个问题是，如果图中存在相同的节点，两种算法是不是就不能工作了？作者回复: 可以的。看你用什么信息去查找 以及怎么定义找到。所谓相同节点 这个说法有点笼统了 怎样才算两个节点相同呢
2018-12-0323
