深度优先搜索

图遍历是按某种系统顺序访问图的所有顶点的问题。遍历图主要有两种方法。

• 广度优先搜索

• 深度优先搜索

深度优先搜索(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 |）

应用领域

• 检测图中的周期

• 查找拓扑排序

• 测试图是否为二部图

• 查找连接的组件

• 寻找图的桥梁

• 在图形中查找双向连接

• 解决骑士之旅

• 仅用一种解决方案即可解决难题