深度优先遍历怎么遍历

深度优先遍历（Depth-First-Search，DFS）是图论中的一种算法。它是沿着图的连通部分一直往下走直到不能再走为止，然后退回到最近的一个可以走的节点，继续走下去重复上述步骤，直至所有的节点都被访问过。那么，深度优先遍历怎么遍历呢？

首先，我们需要明确深度优先遍历的遍历顺序是从一条路径的起点开始一直往下走到底，然后回溯到最后一个分叉口，走另一条路径一直往下走到底，如此反复。因此，在实现深度优先遍历时可以选择递归算法或者非递归算法。

对于递归算法，具体实现是从图的某一顶点v0开始，首先标记该顶点已访问过，然后在v0的邻接结点中任选一个与v0不同的顶点v1，通过递归的方式找到与v1相邻的未被访问过的顶点v2，如此递归下去，直到该顶点的所有邻接结点都被访问过，然后回溯到离v0最近的一层子节点，继续递归到下一个还未被访问的结点。当所有节点都被遍历完成，即得到深度优先遍历序列。需要注意的是，在实现中需要使用一个数组存储每个顶点的遍历状态，初始均为未遍历。

对于非递归算法，通常使用栈进行实现。从图的起点开始遍历，将其入栈并标记为已访问，然后遍历其相邻节点并入栈，继续遍历其中的一个节点直至无法继续下去，栈顶节点出栈，回到上一个节点继续遍历，直至遍历所有节点。需要注意的是，在实现中需要使用一个数组存储每个顶点的遍历状态，初始均为未遍历。

此外，实现深度优先遍历的时间复杂度通常为O(n+m)，其中n为图中的顶点数，m为图中的边数。因为每个顶点和每条边都会被访问一次，因此时间复杂度和图的规模成正比。

综上所述，深度优先遍历可以使用递归算法或者非递归算法进行实现，其中使用栈的非递归算法效率更高。需要注意的是，在实现中应该使用一个数组存储每个顶点的遍历状态，初始均为未遍历。深度优先遍历算法的时间复杂度为O(n+m)，即与图的规模成正比。