图算法表示：广度优先搜索数据结构

Question

我正在完成数据科学硕士学位的数据结构和算法预备课程。

这里是我根据课程中提供的伪代码编写的图的广度优先搜索算法。我才使用python两个月左右，所以还不太熟练。我也没有计算机科学背景。

问题：对于我能得到的任何回复，我将非常感激。

我使用 id 属性来标识每个顶点实例。相反，是否可以将数据属性中的 id 作为键：值对传递。这是假设数据是包含顶点的不同信息的字典。 如果我在创建 Vertex 实例时将 adj_list 列表作为参数传递，则 print_shortestpath() 方法将不起作用。我不知道这是为什么。仅当我在定义列表中所有涉及的顶点后设置 adj_list 时，它才有效。 对于那些有经验的人来说，这就是 BFS 在行业中的使用方式吗？或者您能否提供反馈意见，帮助我更好地实现或编码？我似乎已经牢牢掌握了这个概念，但我不确定我的实现是否标准或高效。例如，伪代码将整个图和源作为 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)

我在创建 Vertex 实例时将 adj_list 列表作为参数传递。

Answer 1

感谢您分享广度优先搜索 (BFS) 算法的 Python 实现以及您深思熟虑的问题。让我们解决您的每个问题，以帮助完善您的代码并理解 BFS 的使用。

在

id

属性中使用

data

是的，如果

id

是字典，您可以将

data

属性中的

data

作为键值对传递。这种方法可以使您的

Vertex

类更加灵活和通用，允许您存储有关每个顶点的各种信息。以下是修改

Vertex

类以支持此功能的方法：

class Vertex:
    def __init__(self, parent=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 else {}
        self.adj_list = adj_list if adj_list else []
        self.id = self.data.get('id', None)  # Get 'id' from data or set to None if not present.

在构造函数中传递

adj_list

时出现问题

当您在

adj_list

实例化期间将

Vertex

作为参数传递时，如果它包含尚未创建的顶点对象，您确实会遇到问题。这是因为 Python 在调用函数（或构造函数）时计算参数，而此时某些顶点对象可能还不存在。

避免此问题的常见方法是在创建所有顶点对象后设置邻接列表，正如您所发现的。或者，您可以先初始化所有没有连接的顶点，然后再添加连接。

标准实践和改进

您的 BFS 实现对于教育目的和中小型项目来说是相当标准的。在工业应用中，尤其是在较大或对性能更加敏感的系统中，BFS 可能是更复杂系统的一部分，或者针对特定用例进行了优化。

以下是一些改进代码的建议：

1. 效率：在

   print_shortestpath

   中使用递归调用，如果图形很大，可能会导致堆栈溢出。更好的方法是使用循环。
2. 关注点分离：将 BFS 操作与

   Vertex

   类解耦。这使您的代码更加模块化和可重用。通常，BFS 是

   Graph

   类中的函数或方法，而不是

   Vertex

   中。
3. 数据完整性：小心可变的默认参数，如

   adj_list=[]

   。这可能会导致意外行为，因为默认参数在定义函数时计算一次，而不是每次调用函数时计算。

这是 BFS 和路径打印方法的修订版本：

def bfs(start_vertex):
    start_vertex.d = 0
    start_vertex.color = "gray"
    queue = Queue()
    queue.put_nowait(start_vertex)
    while not queue.empty():
        u = queue.get_nowait()
        for v in u.adj_list:
            if v.color == "white":
                v.d = u.d + 1
                v.p = u
                v.color = "gray"
                queue.put_nowait(v)
        u.color = "black"

def print_shortest_path(source, destination):
    if source.d == float("inf"):  # BFS not run yet
        bfs(source)
    path = []
    step = destination
    while step is not None:
        path.append(step.id)
        step = step.p
    if path[-1] != source.id:
        print("No path from source to destination.")
    else:
        print(" -> ".join(reversed(path)))

# Example of usage
if __name__ == "__main__":
    # Initialize and connect vertices as shown above
    print_shortest_path(n1, n10)

这些更改将使您的代码更干净、更高效，并且更符合软件开发中的常见实践。