深度优先搜索简介

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

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

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

StackOverflow 文档

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

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

让我们一步一步地看一下: StackOverflow 文档 StackOverflow 文档 StackOverflow 文档 StackOverflow 文档 StackOverflow 文档 StackOverflow 文档

我们可以看到一个重要的关键字这是后来的。你可以看到。 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 表示边数。

深度优先搜索的应用:

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