Python图算法实战：深度优先与广度优先遍历详解

许南星

发布时间：2026-10-13| 6人浏览过

原创

本文深入解析Python中图的深度优先搜索（DFS）和广度优先搜索（BFS）算法。通过回溯概念引入，详细阐述两种算法的执行逻辑，并提供完整的Graph类代码实现及运行结果展示，帮助开发者掌握图结构的核心遍历技术。

算法概述与回溯概念

本文通过具体实例，详细讲解Python中图的深度优先搜索（DFS）和广度优先搜索（BFS）算法的实现原理与代码应用，供读者参考学习。

在深入算法之前，首先需要理解一个核心概念：回溯。

回溯法（探索与回溯法）是一种基于选优条件的搜索策略。它沿着选优条件向前探索，旨在达到目标状态。然而，当探索到某一步发现当前选择并非最优或无法达成目标时，算法会退回上一步重新进行选择。这种“走不通就退回再走”的技术被称为回溯法，而满足回溯条件的特定状态点则被称为“回溯点”。

深度优先搜索（DFS）实现

深度优先算法（DFS）的执行流程如下：

（1）访问初始顶点v，并标记顶点v为已访问状态。（2）查找顶点v的第一个邻接顶点w。（3）判断顶点v的邻接顶点w是否存在：若存在，则继续执行后续步骤；若不存在，则回溯到顶点v，寻找v的另一个未访问过的邻接点。（4）若顶点w尚未被访问，则访问顶点w，并将其标记为已访问。（5）继续查找顶点w的下一个邻接顶点wi，若找到，则返回步骤（3）继续处理；该过程持续进行，直到连通图中的所有顶点均被访问完毕。

广度优先搜索（BFS）实现

广度优先算法（BFS）的执行流程如下：

（1）将初始顶点v加入队列。（2）判断队列是否为空：若队列非空，则继续执行；若队列为空，则算法结束。（3）从队列中出队，获取队头顶点v；访问该顶点v，并标记顶点v为已访问。（4）查找顶点v的第一个邻接顶点col。（5）若顶点v的邻接顶点col未被访问过，则将col加入队列。（6）继续查找顶点v的另一个新的邻接顶点col，并返回步骤（5）处理；该过程持续进行，直到顶点v的所有未被访问过的邻接点均处理完毕，随后返回步骤（2）继续处理队列中的其他顶点。

代码实现与运行结果

以下是上述算法的Python代码实现：


#!/usr/bin/python
# -*- coding: utf-8 -*-
class Graph(object):
  def __init__(self,*args,**kwargs):
    self.node_neighbors = {}
    self.visited = {}
  def add_nodes(self,nodelist):
    for node in nodelist:
      self.add_node(node)
  def add_node(self,node):
    if not node in self.nodes():
      self.node_neighbors[node] = []
  def add_edge(self,edge):
    u,v = edge
    if(v not in self.node_neighbors[u]) and ( u not in self.node_neighbors[v]):
      self.node_neighbors[u].append(v)
      if(u!=v):
        self.node_neighbors[v].append(u)
  def nodes(self):
    return self.node_neighbors.keys()
  def depth_first_search(self,root=None):
    order = []
    def dfs(node):
      self.visited[node] = True
      order.append(node)
      for n in self.node_neighbors[node]:
        if not n in self.visited:
          dfs(n)
    if root:
      dfs(root)
    for node in self.nodes():
      if not node in self.visited:
        dfs(node)
    print order
    return order
  def breadth_first_search(self,root=None):
    queue = []
    order = []
    def bfs():
      while len(queue)> 0:
        node = queue.pop(0)
        self.visited[node] = True
        for n in self.node_neighbors[node]:
          if (not n in self.visited) and (not n in queue):
            queue.append(n)
            order.append(n)
    if root:
      queue.append(root)
      order.append(root)
      bfs()
    for node in self.nodes():
      if not node in self.visited:
        queue.append(node)
        order.append(node)
        bfs()
    print order
    return order
if __name__ == '__main__':
  g = Graph()
g.add_nodes([i+1 for i in range(8)])
g.add_edge((1, 2))
g.add_edge((1, 3))
g.add_edge((2, 4))
g.add_edge((2, 5))
g.add_edge((4, 8))
g.add_edge((5, 8))
g.add_edge((3, 6))
g.add_edge((3, 7))
g.add_edge((6, 7))
print "nodes:", g.nodes()
order = g.breadth_first_search(1)
order = g.depth_first_search(1)

运行程序后，得到的输出结果如下：