深度优先搜索算法教程

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。它沿着树的分支一路向下深入，直到到达叶节点，然后再回溯到上一个节点，继续向下搜索。

基本概念

节点：树或图中的每一个点。
边：连接两个节点的线。
路径：从起点到终点的节点序列。
深度：从一个节点到另一个节点的边的数量。

算法步骤

选择一个起始节点。
访问该节点。
将该节点标记为已访问。
如果该节点有未访问的邻接节点，选择一个邻接节点作为下一个要访问的节点，并重复步骤2-4。
如果没有未访问的邻接节点，回溯到上一个节点，并重复步骤4。

代码示例

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

    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')

            for neighbor in reversed(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')

扩展阅读

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

图片