Depth-First Search (DFS) 算法

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它沿着树的分支一路向下走到最深处，然后再回溯。

DFS 算法原理

DFS 算法的基本思想是从树的根节点开始，沿着一个分支一直走到叶子节点，然后回溯到上一个节点，再沿着另一个分支继续。

DFS 算法步骤

选择一个起点（根节点）。
访问该节点。
将该节点标记为已访问。
对于该节点的每个未访问的邻接节点，递归执行步骤 1-4。
如果没有未访问的邻接节点，则回溯到上一个节点。

DFS 算法示例

假设我们有一个图如下：

A -- B -- C
|     |
D -- E

使用 DFS 算法遍历该图，可能的顺序是 A -> B -> C -> E -> D。

代码示例

以下是一个使用 Python 实现的 DFS 算法示例：

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            print(vertex)
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)

graph = {
    'A': ['B', 'D'],
    'B': ['C', 'E'],
    'C': [],
    'D': ['E'],
    'E': []
}

dfs(graph, 'A')

输出结果为：

A
B
C
E
D

扩展阅读

想要了解更多关于算法的知识，可以访问我们的算法教程页面。