面试刷题：深度优先搜索DFS 頭條網

2021-04-09 05:11:29 佚名

如何遍历一个图式的数据结构？这并不像简单的线性结构那样直观，因此需要确立一种原则，以保证既不缺失又不重复。通常按照探索方向来划分成两种遍历方法，一是优先向深度更大的节点遍历的深度优先搜索(Depth First Search, DFS)；二是优先向同层兄弟节点遍历的广度优先搜索(Breath First Search, BFS)。

在Leetcode中，非常多问题都可以使用DFS来解决，虽然不见得每一个都是高效的，但是了解这种基本的算法能够提升遇到新问题想出解决方案的概率。这里就以【Leetcode Q1376 通知所有员工所需的时间】为例，建议探讨一下DFS。

1 题目 Q1376 通知所有员工所需的时间

公司有 n 名员工，每个员工的唯一ID从 0 到 n-1。公司的负责人是具有 headID 的员工。每个员工在 manager 数组中都有一个直接经理，其中 manager[i] 是第 i 个员工的直接经理，manager[headID] = -1。此外，还确保从属关系具有树结构。公司负责人希望将紧急消息通知公司所有员工。他将通知直属下属，他们将通知其下属，依此类推，直到所有员工都知道紧急消息为止。

第i位员工需要 informTime[i] 分钟来通知其所有直接下属（即，在 inform[i] 分钟之后，他的所有直接下属都可以开始传播新闻）。返回将紧急消息通知所有员工所需的分钟数。

约束条件：

(a) 1 <= n <= 10^5

(b) 0 <= headID < n

(d) 0 <= manager[i] < n

(e) manager[headID] == -1

(f) informTime.length == n

(g) 0 <= informTime[i] <= 1000

(h) 员工 i 没有下线则 informTime[i] == 0

(i)) 要保证所有员工都被通知到

示例 1

<code>Input:
 n
 =
 1
,
 headID
 =
 0
,
 manager
 = 
 [-1],
 informTime
 =
 [0]
Output:
 0
/<code>

解释： 该公司只有一个人，所以通知所需时间为 0。

示例 2

<code>Input:
 n
 =
 6
,
 headID
 =
 2
,
 manager
 =
 [2,2,-1,2,2,2],
 informTime 
 =
 [0,0,1,0,0,0]
Output:
 1
/<code>

解释： id=2的人是管理者，是其他人的上线，因此通知所需时间为 1。

示例 3

<code>Input:
 n
 =
 7
,
 headID
 =
 6
,
 manager
 =
 [1,2,3,4,5,6,-1],
 informTime
 =
  
[0,6,5,4,3,2,1]
Output:
 21
/<code>

解释: id=6的人是最高层的管理者，其他的每个人都分属于不同的层，因此通知需要的时间是每一层管理者所需时间之和。

示例 4

<code>Input:
 n
 =
 15
,
 headID
 =
 0
,
 manager
 =
 [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6],
 informTime
 =
 [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0] 

Output:
 3
/<code>

解释： 所有人的层级关系正好构成一个二叉树，id=0的人为跟节点，遍历所有从跟节点到叶子节点的路径，然后取最大耗时即可。

以上四个示例的示意图如下所示：

四个例子的示意图

2 解决思路

题中的诸多限制都在说明一件事情，人事管理者和下属所形成的结构为树形，即有向无环图(DAG)。这个问题的描述比较复杂，但是所表述的问题结构却是非常简单，即找出树形结构中权重之和最大的路径。只是，这里的树是更一般意义上的树，而不是二叉树或者任何孩子节点数量固定的树。但是，从遍历或者搜索方法上而言，是没有差别的。

我们需要枚举出所有的从最高层到最底层的信息传播路径，然后将每一段路径的耗时相加。按照树的结构讲，就是遍历所有从根节点到叶子节点的路径。

一条完整的路径必然是从根节点到叶子节点的，因此在搜索时，应当优先往叶子节点的方向搜索，也就是深度优先搜索DFS。

针对一棵二叉树，其搜索的大概示意图如下：