深度优先算法DFS入门 (超级简单的例题入门)

2024-07-13 00:28| 来源: 网络整理| 查看: 265

参考文章： 1、Leetcode Subset I & II 作者：算法鱼（里面是java版本的代码） 2、剪枝算法(算法优化) 作者：瞭望天空 3、Leetcode 上面的一些评论和题解

一、什么是 DFS？图的深度优先搜索（Depth First Search），和树的先序遍历比较类似。具体做法是：假设初始状态是图中所有顶点均未被访问，则从某个顶点V出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V有路径相通的顶点都被访问到。若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。显然，深度优先搜索是一个递归的过程。

概念很简单，来看看例题的代码吧！

二、Leetcode 例题：Subsets

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 来源：力扣（LeetCode）

分析一下题目，其实有很多方法解这道题的，暴力法（会超时）、动态规划、DFS… 这里当然将DFS+递归（DFS里面本来就是递归）了。

这道题是要求生成所有子集，那么首先我们有一个能返回所有子集的二维数组results, 和一个临时变量temp（一维数组，初始为空，将他push_back，）, 当temp满足一定条件的时候，往results里面添加结果。

好，开始我们的DFS重头戏了。一起来想象一下，输入的数组是一幅有向图，方向是从大到小。比如说，输入: nums = [1,2,3] 我们把他想象成有向图，进行深度优先搜索，从1开始：（我们先不管代码，先看下面的图片和推导过程）代码解释图

[] //刚开始temp为空集合，空集合影视[1,2,3]的一个子集 [1] //然后我们来到了1 [1

【本文地址】

公司简介

联系我们