图dfs和bfs算法 python

### Python 中实现 DFS 和 BFS 算法

#### 深度优先搜索 (DFS)

深度优先搜索是一种用于遍历或搜索树或图的算法。该算法从根节点开始，尽可能深入子节点进行探索直到达到叶子节点，再回溯至上一层继续未完成的分支。

def dfs(graph, start):
    visited = set()  # 记录访问过的节点
    
    def _dfs(node):
        if node not in visited:
            print(f"Visiting {node}")
            visited.add(node)
            for neighbour in graph[node]:
                _dfs(neighbour)
    
    _dfs(start)

此代码定义了一个内部函数 `_dfs` 来执行实际的递归调用，并通过 `visited` 集合来跟踪已经访问过哪些节点以防止重复访问[^1]。

#### 广度优先搜索 (BFS)

广度优先搜索也是一种用来遍历或搜索树或图结构的方法。它按照层次顺序逐层向外扩展，即先访问离起始点最近的所有顶点，然后再依次向更远距离的地方前进。

from collections import deque

def bfs(graph, start):
    visited = set([start])  # 初始化已访问集合
    queue = deque([start])  # 使用双端队列作为待处理列表
    
    while queue:
        vertex = queue.popleft()
        print(f"Visiting {vertex}")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

这段程序利用了标准库中的 `deque` 类型创建一个双向队列来进行高效地入队和出队操作；同样也维护着一个 `visited` 的记录集以防再次访问相同的节点[^4]。