深度优先搜索（DFS）教程

深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。它沿着树的深度遍历树的节点，直到到达叶子节点为止。

DFS 算法原理

DFS 算法的基本思想是从根节点开始，沿着一条路径一直走到底，如果遇到一个节点没有子节点，则返回到上一个节点，然后沿着另一条路径继续走，直到所有的节点都被访问过。

DFS 算法步骤

选择一个起点。
访问起点，并标记为已访问。
如果起点有未访问的邻接节点，选择一个邻接节点，重复步骤2。
如果没有未访问的邻接节点，返回到上一个节点，并重复步骤3。
重复步骤2-4，直到所有的节点都被访问过。

DFS 算法应用

DFS 算法在计算机科学中有着广泛的应用，例如：

图的遍历
查找路径
检测图的连通性
寻找最小生成树

示例

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

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

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

# 示例图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

dfs(graph, 'A')

运行上述代码，输出结果为：

A
B
D
E
F
C

扩展阅读