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

精选留言(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