深度优先搜索简介

深度优先搜索是用于遍历或搜索树或图数据结构的算法。一个从根开始，并在回溯之前尽可能地沿着每个分支进行探索。19 世纪法国数学家查尔斯·皮埃尔·特雷马斯（CharlesPierreTrémaux）研究了一种深度优先搜索作为解决迷宫的策略。

深度优先搜索是查找从源顶点可到达的所有顶点的系统方法。与广度优先搜索一样，DFS 遍历给定图的连通组件并定义生成树。深度优先搜索的基本思想是有条不紊地探索每个边缘。我们从必要的顶点开始。一旦我们发现了一个顶点，DFS 就会从它开始探索（不像 BFS，它将一个顶点放在一个队列中以便以后从中进行探索）。

我们来看一个例子。我们将遍历此图：

我们将遵循以下规则遍历图表：

• 我们将从源头开始。
• 没有节点将被访问两次。
• 我们尚未访问的节点将是白色的。
• 我们访问过但未访问其所有子节点的节点将显示为灰色。
• 完全遍历的节点将变为黑色。

让我们一步一步地看一下：

我们可以看到一个重要的关键字这是后来的。你可以看到。 5-1 称为后备。这是因为我们还没有完成 node-1 ，所以从另一个节点到 node-1 意味着图中有一个循环。在 DFS 中，如果我们可以从一个灰色节点转到另一个灰色节点，我们可以确定图形具有循环。这是在图中检测循环的方法之一。根据源节点和我们访问的节点的顺序，我们可以找出一个循环中的任何边缘作为后备。例如：如果我们从 1 开始到 5 ，我们就会发现 2-1 作为后备。 **** ****

我们从灰色节点到白色节点的边缘称为树边缘。如果我们只保留树边缘并删除其他边缘，我们将得到 DFS 树。

在无向图中，如果我们可以访问已访问过的节点，那么它必须是一个备份节点。但对于有向图，我们必须检查颜色。当且仅当我们可以从一个灰色节点转到另一个灰色节点时，称为后备。

在 DFS 中，我们还可以为每个节点保留时间戳，这可以以多种方式使用（例如：拓扑排序）。

1. 当节点 v 从白色变为灰色时，时间记录在 d [v]中。
2. 当节点 v 从灰色变为黑色时，时间记录在 f [v]中。

这里 d [] 表示发现时间， f [] 表示结束时间。我们的 pesudo 代码看起来像：

Procedure DFS(G):
for each node u in V[G]
    color[u] := white
    parent[u] := NULL
end for
time := 0
for each node u in V[G]
    if color[u] == white
        DFS-Visit(u)
    end if
end for

Procedure DFS-Visit(u):
color[u] := gray
time := time + 1
d[u] := time
for each node v adjacent to u
    if color[v] == white
        parent[v] := u
        DFS-Visit(v)
    end if
end for
color[u] := black
time := time + 1
f[u] := time

复杂：

每个节点和边都被访问一次。因此 DFS 的复杂度为 O（V + E） ，其中 V 表示节点数， E 表示边数。

深度优先搜索的应用：

• 在无向图中查找所有对最短路径。
• 在图中检测循环。
• 寻找路径。
• 拓扑排序。
• 测试图表是否为二分图。
• 寻找强连接组件。
• 用一种解决方案解决难题。