深度优先搜索
图遍历是按某种系统顺序访问图的所有顶点的问题。遍历图主要有两种方法。
广度优先搜索
深度优先搜索
深度优先搜索(DFS)算法从顶点v开始，然后遍历到之前未访问过的相邻顶点（例如x），并将其标记为“已访问”，然后继续处理x的相邻顶点，依此类推。
如果在任何一个顶点上遇到所有相邻顶点都被访问过，则它将回溯直到找到具有一个之前尚未遍历的相邻顶点的第一个顶点。然后，它遍历该顶点，继续其相邻的顶点，直到遍历所有访问的顶点并必须再次回溯。这样，它将遍历从初始顶点v可以到达的所有顶点。
DFS算法
该概念是在访问其他相邻顶点之前先访问相邻顶点的所有相邻顶点。
将所有节点的状态初始化为“就绪”
将源顶点放在堆栈中，并将其状态更改为“等待”
重复以下两个步骤，直到堆栈为空-
从堆栈中弹出顶部顶点，并将其标记为“已访问”
将状态为“就绪”的已移除顶点的所有邻居推入堆栈的顶部。将其状态标记为“正在等待”。
问题
让我们拍一个图（源顶点为“ a”）并应用DFS算法找出遍历顺序。
解
将所有顶点的状态初始化为“就绪”。
按一个堆栈并将其状态更改为“等待”。
弹出一个并将其标记为“已访问”。
将处于“就绪”状态的e，d和b的邻居推入堆栈的顶部，并将其标记为“正在等待”。
从堆栈中弹出b，将其标记为“已访问”，将其“就绪”邻居c推入堆栈。
从堆栈中弹出c并将其标记为“访问”。它没有“就绪”邻居。
从堆栈中弹出d并将其标记为“已访问”。它没有“就绪”邻居。
从堆栈弹出e并将其标记为“访问”。它没有“就绪”邻居。
堆栈为空。所以停止。
因此遍历顺序为-
a→b→c→d→e
遍历的替代顺序是-
a→e→b→c→d
或a→b→e→c→d
或a→d→e→b→c
或a→d→c→e→b
或a→d→c→b→e
令G(V,E)为| V | 顶点数和| E | 边数。如果DFS算法访问图形中的每个顶点并检查每个边缘，则时间复杂度为-
⊝（| V | + | E |）
应用领域
检测图中的周期
查找拓扑排序
测试图是否为二部图
查找连接的组件
寻找图的桥梁
在图形中查找双向连接
解决骑士之旅
仅用一种解决方案即可解决难题
-
主要内容：深度优先搜索（简称“深搜”或DFS）,广度优先搜索,总结前边介绍了有关图的 4 种存储方式，本节介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种： 深度优先搜索和 广度优先搜索。 深度优先搜索（简称“深搜”或DFS） 图 1 无向图 深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为： 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以
-
3. 深度优先搜索 现在我们用堆栈解决一个有意思的问题，定义一个二维数组： int maze[5][5] = { 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的路线
-
本文向大家介绍什么是深度优先搜索？相关面试题，主要包含被问及什么是深度优先搜索？时的应答技巧和注意事项，需要的朋友参考一下 如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索树。它的基本思想是：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。深度优先搜索
-
深度优先搜索的一般运行时间如下。 dfs 中的循环都在 $$O(V)$$ 中运行，不计入dfsvisit 中发生的情况，因为它们对图中的每个顶点执行一次。 在dfsvisit 中，对当前顶点的邻接表中的每个边执行一次循环。 由于只有当顶点为白色时，dfsvisit 才被递归调用，所以循环对图中的每个边或 $$O(E)$$ 执行最多一次。 因此，深度优先搜索的总时间是 $$O(V + E)$$。
-
骑士之旅是深度优先搜索的特殊情况，其目的是创建最深的第一棵树，没有任何分支。更一般的深度优先搜索实际上更容易。它的目标是尽可能深的搜索，在图中连接尽可能多的节点，并在必要时创建分支。 甚至可能的是，深度优先搜索将创建多于一个树。当深度优先搜索算法创建一组树时，我们称之为深度优先森林。与广度优先搜索一样，我们的深度优先搜索使用前导链接来构造树。此外，深度优先搜索将在顶点类中使用两个附加的实例变量。新
-
在这篇文章中，biziclop为非递归深度优先搜索算法插入了伪代码。 如果我们想使用递归DFS算法来检查节点的适当性，我们可以利用两个变体：pre-order（当一个节点在其子节点之前检查时）和post-order（当子节点在节点之前检查时），加上仅针对二叉树的第三个变体（顺序：左子树，然后节点，然后右子树）。 如果可能的话，我对这三个变体都很感兴趣，所以我试图修改biziclop的伪代码，以便获