Python实现BFS与DFS算法：队列与栈的核心差异解析

小满

发布时间：2026-10-14| 3人浏览过

原创

本文通过Python代码实例对比广度优先搜索（BFS）与深度优先搜索（DFS）的实现。重点解析两者在数据结构上的核心差异：BFS依赖队列（Queue）实现逐层遍历，而DFS利用栈（Stack）进行深度挖掘。通过修改pop操作即可实现算法切换，帮助开发者快速掌握图遍历逻辑及底层原理。

广度优先搜索（BFS）实现

广度优先搜索（BFS）


"""
# @Time  : 2020/11/8
# @Author : Jimou Chen
"""


# 广搜
def bfs(graph, start):
  queue = [start] # 先把起点入队列
  visited = set() # 访问国的点加入
  visited.add(start)

  while len(queue):
    vertex = queue.pop(0)
    # 找到队列首元素的连接点
    for v in graph[vertex]:
      if v not in visited:
        queue.append(v)
        visited.add(v)
    # 打印弹出队列的该头元素
    print(vertex, end=' ')


if __name__ == '__main__':
  graph = {
    'A': ['B', 'D', 'I'],
    'B': ['A', 'F'],
    'C': ['D', 'E', 'I'],
    'D': ['A', 'C', 'F'],
    'E': ['C', 'H'],
    'F': ['B', 'H'],
    'G': ['C', 'H'],
    'H': ['E', 'F', 'G'],
    'I': ['A', 'C']
  }

  bfs(graph, 'A')

输出结果为：A B D I F C H E G Process finished with exit code 0

深度优先搜索（DFS）实现

深度优先搜索（DFS）


"""
# @Time  : 2020/11/8
# @Author : Jimou Chen
"""


# 深搜
def dfs(graph, start):
  stack = [start]
  visited = set()
  visited.add(start)

  while len(stack):
    vertex = stack.pop() # 找到栈顶元素
    for v in graph[vertex]:
      if v not in visited:
        stack.append(v)
        visited.add(v)

    print(vertex, end=' ')


if __name__ == '__main__':
  graph = {
    'A': ['B', 'D', 'I'],
    'B': ['A', 'F'],
    'C': ['D', 'E', 'I'],
    'D': ['A', 'C', 'F'],
    'E': ['C', 'H'],
    'F': ['B', 'H'],
    'G': ['C', 'H'],
    'H': ['E', 'F', 'G'],
    'I': ['A', 'C']
  }

  dfs(graph, 'E')