深度优先遍历经典例题

深度优先遍历（Depth-First Search，DFS）算法是一种重要的搜索算法，通常用于解决图论、树等结构的遍历问题。本文将围绕深度优先遍历算法展开，介绍几个经典例题，并从多个角度对深度优先遍历算法进行分析。

一、深度优先遍历简介

在深度优先遍历算法中，从一条路走到底，直到递归到最深处，然后回溯到根节点，再往其他方向走，重复此步骤直到所有节点都遍历到。基本思想是从一个顶点开始沿着一条路径遍历至该路径最后一个顶点，然后回溯至前一个顶点，再继续遍历下一条路径。深度优先遍历算法可以使用递归实现或者使用栈来模拟。

二、例题1：岛屿数量

题目描述：给定一个由 '1'（陆地）和 '0'（水）组成的网格图，计算岛屿的数量。一个岛被水包围，并且周围四面都是水，被水包围的陆地不算做岛屿。你可以假设网格的四个边都被水包围。

分析：本题需要使用深度优先遍历算法来解决。我们从某一个岛屿的位置出发，访问到该岛屿后，将其标记为已访问，并以该位置为中心向四周深度优先搜索。当四周都没有岛屿或者已经被标记为已访问时，回溯到上一层，并且继续搜索。

关键点：深度优先遍历、标记已访问

三、例题2：员工的重要性

题目描述：给定一个员工信息列表，包括员工 ID、重要性、以及他们的直系下属，每个员工都有一个唯一的 ID，直系下属是一个员工的下属，是他那一级别下的员工。重要度是该员工在公司内的重要性指数，数值越大表示越重要。给定一个 ID，返回这个员工及其所有下属的重要性之和。

分析：本题可以使用深度优先遍历算法和哈希表来解决。首先将员工列表以哈希表的形式存储，以员工 ID 为键，以员工信息为值。然后从给定员工的 ID 出发，使用深度优先遍历算法搜索其所有下属，计算出他的重要性之和。

关键点：哈希表、深度优先遍历

四、例题3：单词拆分

题目描述：给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判断 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

分析：本题可以使用深度优先遍历算法和 动态规划算法 来解决。深度优先遍历算法的思路是从字符串的开头开始搜索，逐步分解字符串，然后在字典中搜索是否有匹配的单词，如果有，深度遍历搜索其余字符串。而动态规划算法则是优先遍历短字符串，通过计算较小的字符串是否可分为单词，获取问题的最优解。

关键点：深度优先遍历、动态规划