python dfs算法

DFS（深度优先搜索）是一种基于栈实现的、递归或非递归的搜索算法。它从起点开始，一直走到不能走为止，然后回退一步继续走，直到所有的路径都被探索完为止。下面是 Python 实现的 DFS 算法示例：

# 定义一个图类
class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adj_list = {v: [] for v in vertices}

    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        self.adj_list[v].append(u)

# DFS 函数
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 graph.adj_list[vertex]:  # 遍历相邻节点
                if neighbor not in visited:  # 如果没有被访问过
                    stack.append(neighbor)  # 将其加入栈中

使用方法：

graph = Graph(['A', 'B', 'C', 'D', 'E', 'F', 'G'])
graph.add_edge('A', 'B')
graph.add_edge('A', 'C')
graph.add_edge('B', 'D')
graph.add_edge('B', 'E')
graph.add_edge('C', 'F')
graph.add_edge('C', 'G')

dfs(graph, 'A')  # 从节点 A 开始遍历

输出结果：

A C G F B E D