图深度遍历是什么

深度优先搜索算法，又称深度优先遍历，简称DFS。它是一种用于遍历或搜索树或图的算法。具体来说，从根结点开始，首先访问一个未被访问过的子结点，然后继续访问该子结点的子结点，直到子结点都被访问过了，然后回溯到当前访问结点的前一个结点，继续访问其它子结点，一直重复这个过程，直到所有结点都被访问过为止。

图深度遍历和树深度遍历类似，只不过是应用在图上，与广度优先搜索算法（BFS）相对。在图论中，深度优先搜索常被用于生成连通性分析、拓扑排序以及临近点生成的方法中。深度优先搜索策略与广度优先搜索策略不同，它偏向于使用递归以及栈结构实现，而广度优先搜索策略使用的是队列结构。

从算法实现的角度来看，深度优先搜索算法有两种实现方法，递归和非递归（栈方式）。

下面我们就来具体讲解一下深度优先搜索算法的思路和实现。

一、深度优先搜索算法遍历方法

1.递归方式

深度优先遍历递归算法的思路：通过递归实现整张图的遍历，具体解释如下：

先构造一个visited数组用于记录所有顶点的访问情况，初始化为False；

从起始顶点开始，先将该顶点的visited值赋为True，然后将该顶点加入到已访问的顶点集合visited中；

对于起始顶点的所有未被访问过的邻接点，依次递归调用DFS，直到没有未被访问的邻接点为止；

若存在从起始顶点可达的未被访问的顶点，按照与第二步类似的方式进行访问；

2.非递归方式

深度优先遍历非递归算法的思路：通过栈的数据结构，实现图的深度优先遍历。具体解释如下：

在遍历过程中，首先选定一个顶点，并将该顶点压入一个栈中；

然后，若该顶点有未被访问的邻接点，则选择其中的一个，进行访问，并将该顶点压入栈中，否则，将该顶点从栈中弹出；

以上两个步骤重复执行，直到栈为空。

二、深度优先搜索实现的注意事项

在深度优先搜索算法的实现过程中，需要注意以下几个问题：

1. 图的连通性

深度优先搜索算法必须考虑到图的连通性，否则可能会导致没有访问到某些点。

2. 采用递归方式时的Python代码实现

递归方式相比于非递归方式，其Python代码实现相对简单。具体如下：

```python

def dfs(graph, start, visited=None):

if visited is None:

visited = set()

visited.add(start)

for next_node in graph[start] - visited:

dfs(graph, next_node, visited)

return visited

```

3. 采用非递归（栈）方式时的Python代码实现

深度优先遍历非递归算法需要使用栈数据结构实现，采用Python语言实现的代码如下：

```python

def dfs_nonrecursive(graph, start):

stack, seen = [start], set()

while stack:

vertex = stack.pop()

if vertex not in seen:

seen.add(vertex)

stack.extend(graph[vertex] - seen)

return seen

```