【原】python‖深度优先搜索（DFS）

深度优先搜索的基本实现：

python

# 定义图结构

graph = {

    'A': ['B', 'C'],

    'B': ['D', 'E'],

    'C': ['F'],

    'D': [],

    'E': ['F'],

    'F': []

}

# 深度优先搜索函数

def dfs(graph, node, visited):

    if node not in visited:

        print(node, end=" ")

        visited.add(node)

        for neighbour in graph[node]:

            dfs(graph, neighbour, visited)

# 使用dfs函数

visited = set() # 使用集合存储访问过的节点

dfs(graph, 'A', visited)

这段代码中，我们首先定义了一个简单的图结构graph。然后定义了一个深度优先搜索的函数dfs。这个函数接受一个图、一个节点和一个已访问节点的集合作为参数。如果节点没有被访问过，我们就将其打印出来，并将其加入到已访问节点的集合中。然后，对于这个节点的每一个邻居节点，我们递归地调用dfs函数。

在这个例子中，我们的图有6个节点（'A'，'B'，'C'，'D'，'E'和'F'），其中'A'是源节点。在调用dfs函数时，我们从'A'开始遍历这个图。