图的迭代深度优先遍历

深度优先搜索（DFS）是一种遍历图的方法，与树的先序遍历类似。下面是先序遍历的递归实现。

图的深度优先遍历（或搜索）与树的深度优先遍历（DFS）相同。唯一的区别是，与树不同，图可能包含循环，因此一个节点可能会被访问两次。使用一个布尔型 visited 数组来防止一个节点被处理多次。

输入： n = 4, e = 6

0 -> 1, 0 -> 2, 1 -> 2, 2 -> 0, 2 -> 3, 3 -> 3

输出： 从顶点 1 开始的 DFS：1 2 0 3

说明

DFS 图

输入： n = 4, e = 6

2 -> 0, 0 -> 2, 1 -> 2, 0 -> 1, 3 -> 3, 1 -> 3

输出： 从顶点 2 开始的 DFS：2 0 1 3

说明

DFS 图

解决方案

• 深度优先搜索算法用于遍历或搜索树或图数据结构。该算法从根节点（或者，在图的情况下，从任意节点）开始，沿每个分支尽可能深入地前进，然后再回溯。因此，基本思想是从根节点或任意节点开始，标记该节点，然后前进到下一个未标记的节点，依此类推，直到没有附近的未标记节点为止。然后回过头来寻找任何其他未标记的节点进行遍历。最后，打印路径节点。
• 迭代 DFS 和递归 DFS 的主要区别在于，递归堆栈已被节点堆栈替换。

算法

• 生成一个节点堆栈并访问一个数组。
• 将根节点压入堆栈。
• 运行一个循环，直到堆栈不为空。
• 弹出堆栈中的元素后打印它。
• 标记当前节点，并将其添加到堆栈中，以遍历每个相邻且未访问过的节点。

迭代 DFS 实现

• 这与 BFS 类似，不同之处在于队列已被堆栈替换。

C++ 程序

输出

Depth First Traversal is shown below:
0 3 2 1 4

• 时间复杂度为 **O(V + E)**，其中 V 是图中的顶点数，E 是边数。
• 空间复杂度为 **O(V)**，因为需要一个大小为 V 的额外 visited 数组。

对先前解决方案的改进

需要注意的是，先前的实现只输出可从给定顶点到达的顶点。例如，如果边 0-3 和 0-2 被删除，则上述代码将只打印 0。调用 DFS 遍历每个未访问过的顶点，以输出图的所有顶点。

C++ 中的实现

输出

Depth First Traversal is shown below:
0 1 2 3 4

• 时间复杂度为 **O(V + E)**，其中 V 是图中的顶点数，E 是边数。（与递归遍历相同）