数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?

王争 2018-12-03
上一节我们讲了图的表示方法,讲到如何用有向图、无向图来表示一个社交网络。在社交网络中,有一个六度分割理论,具体是说,你与世界上的另一个人间隔的关系不会超过六度,也就是说平均只需要六步就可以联系到任何两个互不相识的人。
一个用户的一度连接用户很好理解,就是他的好友,二度连接用户就是他好友的好友,三度连接用户就是他好友的好友的好友。在社交网络中,我们往往通过用户之间的连接关系,来实现推荐“可能认识的人”这么一个功能。今天的开篇问题就是,给你一个用户,如何找出这个用户的所有三度(其中包含一度、二度和三度)好友关系?
这就要用到今天要讲的深度优先和广度优先搜索算法。

什么是“搜索”算法?

我们知道,算法是作用于具体数据结构之上的,深度优先搜索算法和广度优先搜索算法都是基于“图”这种数据结构的。这是因为,图这种数据结构的表达能力很强,大部分涉及搜索的场景都可以抽象成“图”。
图上的搜索算法,最直接的理解就是,在图中找出从一个顶点出发,到另一个顶点的路径。具体方法有很多,比如今天要讲的两种最简单、最“暴力”的深度优先、广度优先搜索,还有 A*、IDA* 等启发式搜索算法。
我们上一节讲过,图有两种主要存储方法,邻接表和邻接矩阵。今天我会用邻接表来存储图。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(102)

  • Jerry银银
    朗读者原谅我的有强迫症:queue这个单词读错了,付上正确的音标如下[kju]

    我觉得避免这种问题,有个方法就是,朗读之前,逐个查询一下单词的正确发音,一篇文章中的单词屈指可数,这个工作量按理说应该不大。

    但是这个简单的举措,能大大提高听文章的体验,不然听起来总觉得很怪

    往大了说影响,毕竟咱们极客时间做的是知识,做的是学问

    作者回复: 😂

    2018-12-03
    3
    110
  • The Sword of Damocles
    看的费劲的同学可以先去网上找找二叉树的深度、广度优先遍历看看。图的搜索和这个类似。
    深度:借助一个栈
    广度:借助一个队列

    老师的代码没有注释,变量名称也比较简洁,虽然下文有解释,但是来回上下翻实在是看的费劲。建议能稍微优化一下。
    2018-12-16
    1
    66
  • P@tricK
    思考题:
    1. 可以。DFS递归时传多一个离初始节点的距离值,访问节点时,距离超过3的不再继续递归

    2. 初始化两个顶点为迷宫起点和终点,从起点开始,遇到分叉点,为每个分支都新建一个节点,并和前一节点连接,递归每个分支直到终点
    2018-12-03
    53
  • 李东勇
    老师, 我觉得深度优先搜索的代码中有一个可以改进的地方, 可以在21行之后加一句: if (found == true) return; 这样, 在一个顶点的for循环之中, 如果已经找到了t, 就可以跳出这个for循环了。目前的逻辑是, 这个for循环中剩下的还会继续执行, 每次都调用一次recurDfs函数, 但recurDfs函数在第一行就return了。

    作者回复: 嗯嗯 👍

    2018-12-18
    24
  • 五岳寻仙
    课后思考题:
    1. 深度优先用于寻找3度好友,可以设定搜索的深度,到3就向上回溯。正如文中提到的,可能不是最短路径,所以会涉及到更新结点度的问题。

    2. 关于迷宫存储问题。类似于欧拉七桥问题,需要将迷宫抽象成图,每个分叉路口作为顶点,顶点之间连成边,构成一张无向图,可以存储在邻接矩阵或邻接表中。
    2018-12-03
    17
  • 唯她命
    老师,你好,我怎么觉得,递归完成之后,回溯到上一步,需要执行visited[w] = false呢,,因为路径不通,所以要回溯,但是应该重置为false,以便下次搜索
    2018-12-21
    1
    7
  • Jerry银银
    留言笔记不小心被自己删了(问了客服,也不能找回了),补上:

    1. 可以用深度遍历,每次遍历到三度人脉,再回溯到上层节点,直到所有的三度人脉都找完。

    2. 将迷宫的每个岔口记为"顶点",岔口之间的路径记为"边",可以用邻接表存储,也可以用邻接矩阵存储。但是个人感觉,像那种标准的方格迷宫,适合用邻接矩阵存储,因为稠密度比较高。
    2018-12-03
    1
    7
  • 我的想法:迷宫可以用带权无向图存储,每个多岔路口是一个顶点,相邻的多岔路口是一条边。带权是为了记录两个顶点间的距离。

    但用上面这种方式,会丢失一些拐点信息。可以结合业务场景,如果需要这些信息,就把拐点也作为一个顶点存储。
    2018-12-03
    6
  • 德尼
    说几个自己觉得是问题的小问题噢。在无向图代码中 adj声明的每个顶点的类型不是Integer吗?怎么在下面赋值时变成了LinkList?
    还有就是语音上在讲述dfs空间复杂度的时候,听到的是dfs的时间(实质上是空间)复杂度为Ov。
    2019-01-02
    5
  • luo
    老师针对图这个数据结构的应用 我有点疑惑,从结构来看无论是临近矩阵还是临近表 其实都需要有一个唯一下标作为这个顶点,那么问题来了 在实际数据量庞大的时候,这种数据结构是不是就没法用了(临近矩阵就不说了,临近表的话也是需要一个大的数组存储每个顶点 ),或者只能拆成以hash先分id,之后映射到对应的机器上存储各自的临近表部分,但这样进行深度广度搜索就有网络io了。

    作者回复: 你说的没错,但是做工程就是trade-off,只能权衡来选择方案。如果实在存不下,可以降低些执行效率。不过,现在有很多图数据库,也可以解决你说的问题,把图直接存在硬盘中。

    2019-01-04
    4
  • Laughing_Lz
    我基础非常差,写了老半天的非递归深度优先遍历,还请各位看看写的对不对

    /**
    * 深度优先遍历
    *
    * @param start 路径查找起始点
    * @param end 路径查找终点
    */
    public void depthFirstSearch(int start, int end) {
    if (start == end) {
    return;
    }
    // 定义一个visited数组,保存是否访问过
    boolean[] visited = new boolean[v];
    // 定义一个栈,作为一个后进先出栈,保存已访问,但相连节点未访问的节点
    Stack<Integer> stack = new Stack<Integer>();
    // 先将start压入栈中
    visited[start] = true;
    stack.push(start);
    while (!stack.isEmpty()) {
    // 取出,但不出栈
    int step = stack.peek();
    // 标识位,标识step节点下的邻接节点中是否有未走过的节点
    boolean hasNoVisited = false;
    for (int i = 0; i < adj[step].size(); i++) {
    int nextStep = adj[step].get(i);
    // 存在未走过节点,则flag = true,将nextStep压入栈中,继续前行
    if (visited[nextStep] == false) {
    hasNoVisited = true;
    visited[nextStep] = true;
    stack.push(nextStep);
    if (nextStep == end) {
    return;
    }
    break;
    }
    }
    // 邻接的节点都是已走过的,则出栈
    if (hasNoVisited == false) {
    stack.pop();
    }
    }
    // 遍历输出栈中存储的节点,即路径
    if (!stack.isEmpty()) {
    Iterator<Integer> it = stack.iterator();
    while (it.hasNext()) {
    System.out.print(it.next() + " ");
    }
    }
    }
    2018-12-13
    4
  • -W.LI-
    弱弱的问一句,prev和visited用数组存是正好value和下标一致才行的吧?

    作者回复: 是的

    2019-10-20
    3
  • Liam
    对于今天的问题,无权图,如果采用深度优先。拿到的路径不一定是最短路径吧

    作者回复: 不是最短路径的。广度优先可以取到最短路径。

    2019-02-13
    2
  • JzyCc
    弱弱的问一下,宽搜代码那块,如果给的图中 1 和 3的位置互换,那么得出来的就不是最短路径了吧

    作者回复: 不,宽搜对于无权图来说,肯定能找到最短路径的。因为整体的逻辑是离起点越近的,越早被访问到。

    2019-02-09
    2
  • qinggeouye

    思考题 2、图的特点:顶点和边(顶点之间的连接关系)。

    迷宫,选一个入口作为起始顶点,遇到岔路口,将岔路口作为顶点,并建立连接关系(边),终止条件应该是:到出口 或者 到下一个路口之后不能再前进为止。这里仍然用深度优先搜索的方法实现。
    2018-12-30
    2
  • + +
    广度优先 有点像树中的层序遍历啊 也是借助一个队列来实现的
    2018-12-05
    2
  • 他在她城断了弦
    可不可以这样理解,深度优先用递归思想,广度优先用迭代思想?

    作者回复: 不大行 因为深度优先也可以用非递归的方式实现

    2018-12-04
    1
    2
  • 猫头鹰爱拿铁
    我感觉用深度优先查找人脉的算法可能会把小于这个度数的数据查找出来吧,例如查找度数为3的顶点,用文中广度优先搜索的那个数据,使用深度优先的算法会把0,1,4,3也给查出来。。。
    2018-12-03
    2
  • Smallfly
    老师把广度和深度优先搜索讲的真的是通俗易懂。我有个问题是,如果图中存在相同的节点,两种算法是不是就不能工作了?

    作者回复: 可以的。看你用什么信息去查找 以及怎么定义找到。所谓相同节点 这个说法有点笼统了 怎样才算两个节点相同呢

    2018-12-03
    1
    2
  • NeverMore
    深度与广度应该都是可以互相实现的,主要复杂度问题。深度主要使用栈,广度主要使用堆。
    2018-12-03
    2
收起评论
99+
返回
顶部