深度优先搜索是笔试面试中重点考察的内容。今天来讲解深度优先搜索的思想。这里推荐阅读《算法笔记》这本数，对考研机试和找工作中笔试面试常考算法都进行了通俗的讲解。公众号回复 801 获取 pdf。

  深度优先搜索的思路很简单，以当前位置为起点，沿着一条路向前走，遇到岔路口，选择一条岔路前进。如果选择的这个岔路是死路（遇到了递归边界），那么就退回到刚刚的岔路口，选择另一个岔路口前进。如果岔路中存在新的岔路，那么也按照刚刚的方法枚举。这样一定能找到出口（目标解存在的情况下）。由于这种方法是不到死路（递归边界）不回头，因此是深度优先。

  深度优先搜索过程中通常会考察剪枝。因为深度优先搜索会搜索每一个可能的路径，复杂度很高，如果在一个岔路口能提前判断某条岔路下面不可能有出口（目标解），就能提前剪枝，跳过对这条岔路的搜索，降低复杂度。

  了解了深度优先搜索的基本思想之后，下面通过几道题来进行练习。

1.力扣133.克隆图^[1]

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {   public int val;   public List neighbors; }

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：

示例 2：

示例 3：

示例 4：

这道题可以用 DFS 很容易的做出来。沿着一条路向前，每次碰到节点就复制，并转向一条岔路，继续复制岔路的节点。如果这条岔路的所有节点都完成了复制，就返回之前的岔路口（节点），转型另一条岔路。代码如下：

2.力扣200.岛屿的数量^[2]

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

示例 2：

这也是一道典型的 DFS 的题。每次遇到陆地（值为 1）是一个岔路口，有 4 条岔路，即上下左右。分别沿着这四条岔路继续前进，直到遇到死路（边界或水）才返回。为了避免重复访问，也需要设置 visited 数组标记改节点是否被访问过，或者直接将 1 改为 0：

Reference

[1]力扣133.克隆图：https://leetcode-cn.com/problems/clone-graph [2]力扣200.岛屿的数量：https://leetcode-cn.com/problems/number-of-islands

    以上就是本篇文章【【算法】深度优先搜索（DFS）】的全部内容了，欢迎阅览 ！ 文章地址：http://syank.xrbh.cn/news/10539.html 
     资讯      企业新闻      行情      企业黄页      同类资讯      首页      网站地图      返回首页 迅博思语资讯移动站 http://kaire.xrbh.cn/ , 查看更多