图BFS算法Python实现疑问与优化咨询

我正在攻读数据科学硕士预科的《数据结构与算法》课程，接触Python仅两个月且无计算机科学背景，基于课程伪代码实现了图的广度优先搜索（Breadth-first search，BFS）算法，有以下疑问：

1. 当前用id属性标识Vertex实例，能否将id作为键值对存入data字典（假设data为存储顶点信息的字典）？
2. 若创建Vertex实例时传入adj_list参数，print_shortestpath()方法失效，仅在所有相关顶点定义后设置adj_list才正常，原因是什么？
3. 该实现是否符合工业界标准？如何优化？例如课程伪代码将整个Graph和源点作为BFS参数，我直接从源Vertex对象调用BFS，是否合理？

附完整Python代码：

from queue import Queue

class Vertex:
    """
    Attributes:
      d: distance. This variable is relative, depending on the source and destination vertexes in a breadth-first or depth-first search
      color: vertex color
      p: parent vertex
      key: key
      data: satellite data added to the vertex datastructure
      adj_list: the adjacency list containing the edges to which this vertex is connected
      id: a str name to identify the vertex
    """

    def __init__(self, parent = None, id = None, key = None, data = None, adj_list = []):

        self.d = float("inf")
        self.color = "white"
        self.p = parent
        self.key = key
        self.data = data
        self.adj_list = adj_list
        self.id = id

    def BFS(self):
        #initializing the attributes of the source vertex
        self.d = 0
        self.color = "gray"
        #creating a queue for enqueing and dequeing the discovered vertexes
        Q = Queue()
        Q.put_nowait(self)
        while not Q.empty():
            u = Q.get_nowait()
            for v in u.adj_list:
                if v.color == "white":
                    v.d = u.d + 1
                    #setting the parent here also helps with finding the shortest path between vertices.
                    v.p = u
                    v.color = "gray"
                    #enqueing the discovered vertex after changing its color to gray.
                    Q.put_nowait(v)
            u.color = "black"

    def print_shortestpath(self, destination_vertex, bfs = False):
        """
        Args:
          bfs: Breadth-first search is needed. This boolean variable tells
          the function whether to run BFS (if it has already been run) or not.

        Returns:
        """
        #conduct a BFS first to map out the different paths from the source to all vertices

        # since recursion is used, this conditional statment makes sure BFS() is called
        #only once for efficiency.

        if bfs == False:
            self.BFS()
        else:
            pass

        if self == destination_vertex:
            #we have gotten to the source from the destination
            #return
            print(self.id)
            return self

        elif destination_vertex.p == None:
            print("No path from the source to the destination vertex exists")
        else:
            #recursive call to the parent of the destination vertex with bfs set to True
            self.print_shortestpath(destination_vertex.p, bfs = True)
    
        print(destination_vertex.id)

#testing it out
if __name__ == "__main__":
    #creating the vertexes
    n1 = Vertex(id="n1")
    n2 = Vertex(id="n2")
    n3 = Vertex(id="n3")
    n4 = Vertex(id="n4")
    n5 = Vertex(id="n5")
    n6 = Vertex(id="n6")
    n7 = Vertex(id="n7")
    n8 = Vertex(id="n8")
    n9 = Vertex(id="n9")
    n10 = Vertex(id="n10")

    #creating the adjacency_list representations of the graph
    #connectin vertices to edges
    n1.adj_list = [n2, n3, n4]
    n2.adj_list = [n1, n5, n9]
    n3.adj_list = [n5, n7, n1]
    n4.adj_list = [n9, n7]
    n5.adj_list = [n2, n3, n6, n8]
    n6.adj_list = [n5, n7, n8]
    n7.adj_list = [n3, n6, n4]
    n8.adj_list = [n5, n6]
    n9.adj_list = [n2, n4, n10]
    
    n1.print_shortestpath(n10)

问题1解答 #

当然可以把id存入data字典。这样做能将顶点的标识信息和其他卫星数据统一管理，让Vertex类的属性更简洁。实现方式有两种：

• 初始化时存入：修改__init__方法，若data为空则创建字典并写入id：

  def __init__(self, parent=None, id=None, key=None, data=None, adj_list=None):
      # ... 其他属性初始化
      if data is None:
          data = {}
      if id is not None:
          data['id'] = id
      self.data = data
  

• 后续手动存入：在创建实例后，直接给data字典赋值：

  n1 = Vertex(id="n1")
  n1.data['id'] = n1.id
  

这种调整不会影响原有功能，还能让data成为顶点所有自定义信息的统一载体，更符合数据结构化的设计思路。

问题2解答 #

这是Python中默认参数为可变对象的经典陷阱。你当前__init__方法中把adj_list = []作为默认参数，意味着所有未传入adj_list的Vertex实例会共享同一个空列表。当你创建实例时传入还未定义的顶点（比如n1 = Vertex(adj_list=[n2])但n2尚未创建），或者后续修改这个共享列表时，会导致多个实例的adj_list互相干扰，甚至引用未初始化的对象，最终BFS无法正确遍历邻接顶点，导致print_shortestpath找不到路径。

解决方法 #

把默认参数改为None，并在初始化时创建独立的空列表：

def __init__(self, parent=None, id=None, key=None, data=None, adj_list=None):
    self.d = float("inf")
    self.color = "white"
    self.p = parent
    self.key = key
    self.data = data if data is not None else {}
    # 为每个实例创建独立的邻接表
    self.adj_list = adj_list if adj_list is not None else []
    self.id = id

此外，创建实例时传入adj_list必须确保所有邻接顶点已经定义，否则会出现引用未定义对象的错误——这也是你后续逐个设置adj_list能正常运行的原因：此时所有顶点都已创建完成，引用不会出问题。

问题3解答 #

是否符合工业界标准？ #

当前实现更偏向教学场景，和工业界标准存在明显差距：

• 缺少统一的Graph类管理所有顶点，图的结构分散在各个Vertex实例的adj_list中，难以统一维护（比如添加/删除顶点、批量重置BFS状态）。
• BFS和print_shortestpath是Vertex的方法，每次运行会修改顶点的永久属性（d、color、p），若多次以不同源点运行BFS，必须手动重置这些属性，否则会出现逻辑错误。
• 递归实现的print_shortestpath在路径较长时会触发Python的递归深度限制，导致栈溢出。

优化方向 #

1. 新增Graph类：用Graph类统一管理顶点（比如用字典存储顶点id -> Vertex实例的映射），将BFS作为Graph的方法，接收源点id作为参数。这样可以方便地批量重置所有顶点的BFS状态，也更符合面向对象的设计逻辑。
2. 分离BFS状态与顶点属性：不要把d、color、p作为Vertex的永久属性，而是在BFS运行时用临时字典存储这些状态，避免污染顶点本身的数据。
3. 迭代实现print_shortestpath：将递归改为迭代，避免栈溢出问题，同时提升运行效率。
4. 添加参数合法性检查：比如在BFS前验证源点是否存在于图中，邻接顶点是否属于当前图等。

从源Vertex调用BFS是否合理？ #

从教学角度看，这种实现没问题，能直观展示BFS从源点出发的遍历过程。但从工业界工程化角度，这种设计不够灵活和健壮：

• 无法处理跨图的顶点引用（比如一个顶点同时属于多个图的场景）。
• 难以统一管理BFS状态，多次调用需手动重置每个顶点的d、color、p属性，容易出错。
• 扩展性差，后续添加DFS、Dijkstra等算法时，无法复用Graph的顶点管理逻辑。

内容的提问来源于stack exchange，提问作者Marrtinerz