DFS python

DFS是深度优先搜索（Depth-First Search）的缩写，是一种用于图遍历或搜索的算法。它以深入系统地搜索图的顶点，直到找到目标顶点或达到无法进一步搜索的叶子节点。DFS的基本思想是从一个初始顶点开始，逐步向下遍历图中的所有相邻顶点，直到无法继续前进为止，然后回溯到前一个顶点，继续遍历其他未遍历的顶点，直到所有顶点都被访问。

在Python中，可以使用递归或栈来实现DFS算法。递归方法通过递归调用自身来遍历图，而栈方法则使用一个辅助栈来模拟递归调用的过程。

递归实现DFS的代码示例如下：

def dfs(graph, start, visited):
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# 示例用法
graph = {
    "A": ["B", "C"],
    "B": ["A", "C", "D"],
    "C": ["A", "B", "D", "E"],
    "D": ["B", "C", "E", "F"],
    "E": ["C", "D"],
    "F": ["D"]
}
start_node = "A"
visited_nodes = set()
dfs(graph, start_node, visited_nodes)

栈实现DFS的代码示例如下：

def dfs(graph, start):
    visited = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(graph[node] - visited)
    return visited

# 示例用法
graph = {
    "A": {"B", "C"},
    "B": {"A", "C", "D"},
    "C": {"A", "B", "D", "E"},
    "D": {"B", "C", "E", "F"},
    "E": {"C", "D"},
    "F": {"D"}
}
start_node = "A"
visited_nodes = dfs(graph, start_node)