python 深度优先搜索算法，DFS

---

前言

什么是深度优先搜索算法（DFS）？

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在DFS中，我们会沿着一个分支走到底，直到该路径上的最后一个节点被访问，然后回溯并沿着另一条路径走到底，这个过程会一直重复，直到所有的节点都被访问过。

---

在Python中实现深度优先搜索，通常会使用递归或栈这两种方式。

使用递归的深度优先搜索

以下是使用递归实现深度优先搜索的一个简单例子。这个例子中，我们假设数据结构是一个无向图，用邻接表来表示。

代码如下（示例）：

def dfs_recursive(graph, node, visited):
    if node not in visited:
        print(node)  # 访问节点
        visited.add(node)
        for neighbour in graph[node]:
            dfs_recursive(graph, neighbour, visited)

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

visited = set()  # 用于记录已访问的节点
dfs_recursive(graph, 'A', visited)

在这个例子中，我们定义了一个递归函数dfs_recursive，它接受一个图graph、一个起始节点node和一个已访问节点的集合visited。如果当前节点node不在已访问集合中，我们打印该节点，将其添加到已访问集合中，并递归地调用dfs_recursive函数对每个邻居节点进行处理。

使用栈的深度优先搜索

代码如下（示例）:

def dfs_stack(graph, start_node):
    visited = set()
    stack = [start_node]

    while stack:
        node = stack.pop()
        if node not in visited:
            print(node)  # 访问节点
            visited.add(node)
            stack.extend(graph[node])

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

dfs_stack(graph, 'A')

---

在这个例子中，我们定义了一个非递归函数dfs_stack，它使用栈来存储待访问的节点。我们首先将起始节点压入栈中，然后进入一个循环，不断从栈中弹出节点进行处理。如果当前节点尚未被访问，我们将其添加到已访问集合中，并将它的邻居节点压入栈中。

总结

两种方法都能有效地实现深度优先搜索。递归的方式代码更简洁，但使用栈的方式可能更直观，并且可以更好地控制搜索过程。

下载链接

源代码下载