算法学习宝典_8_dfsbfs

一、DFS
什么是深度优先搜索？
深度优先搜索是用来遍历或搜索树和图数据结构的算法，它是可以从任意跟节点开始，选择一条路径走到底，并通过回溯来访问所有节点的算法。简单来说就是通过选择一条道路走到无路可走的时候回退到上一个岔路口，并标记这条路已走过，选择另外一条道路继续走，直到走遍每一条路。
深度优先搜索的思想
Dfs思修基于递归思想，通过递归的形式来缩小问题规模，把一件事分割成若干个相同的小事，逐步完成。
深度优先搜索的步骤分为 1.递归下去2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。

否则既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。

Dfs有两个重要标志，也就是两个重要数组，一个是标记数组，标记该点是否被访问过，一个用来把该点放入数组，两个点是相辅相承的，通过放入一个起点，并标记起始点，然后依次搜索附近所有能访问的结点，用递归走到下一个点，重复这个步骤，直到走到目标点或是走完全图。

深度优先搜索的时间复杂度：
在深度优先搜索算法中，每条边最多会被访问两次，一次是遍历，一次是回退。所以，深度优先搜索的时间复杂度为 O(E)

< 后面补上 dfs C语言模板 及 bfs 说明， 还有多源BFS 算法 ，比较常用>

leetcode :

207. 课程表 -->有点顶
394. 字符串解码 --> 用栈解决的
491. 递增子序列
490. 迷宫
499迷宫
582. 杀掉进程
130. 被围绕的区域
1239. 串联字符串的最大长度
254. 因子的组合
994. 腐烂的橘子
1162. 地图分析
515. 在每个树行中找最大值
743. 网络延迟时间
200. 岛屿数量
542. 01 矩阵
934. 最短的桥