Python

Question

我正在尝试实现 Graph 和 bfs（广度优先搜索）算法。我有这个 graph_object class:

class Vertex:
    def __init__(self,id):
        self.id=id #just a character representing each node/vertex name e.g. 'a', 'b'...
        self.neighbors=[]
        '''list of adjacent vertices. we call them neighbors. 
        d.neighbors=[b,c,g]. 
        note that here we are talking about the Vertex objects b,c,g. Not their corresponding vertex IDS ('b', 'c' and 'g')
        '''
        self.parent=None
        '''parent of a vertex depends on order of visit of the vertices in a graph.  

        calling the function bfs() on above graph will assign a.parent=None, b.parent=a , c.parent=d, d.parent=b, g.parent=d '''
    def __str__(self):
        return "{}:{}".format(self.id,self.get_neighbors()) #
    def get_neighbors(self):
        return [v.id for v in self.neighbors]
    def get_id(self):
        return self.id
    def get_parent(self):
        return self.parent
    def add_neigbor(self,v):
        self.neighbors.append(v)

class Graph:
    def __init__(self):
        self.vertices={}
        self.num_vert=0
    def get_vertex(self,v_id):
        if v_id not in self.get_vertices():
            return None
        else:
            return [v for v in self.vertices if v.id==v_id].pop(0) #to understand what happens here, refer to dict_exercise.py
    def add_vertex(self,v_id):
        if v_id not in self.get_vertices():
            new=Vertex(v_id)
            self.vertices[new]=new.neighbors
    def add_edge(self,v1_id,v2_id):
        if v1_id not in self.get_vertices():
            self.add_vertex(v1_id)
        if v2_id not in self.get_vertices():
            self.add_vertex(v2_id)
        #vertices with IDs v1_id and v2_id are now guaranteed to exist in graph, we get the corresponding vertex objects v1 and v2
        v1=self.get_vertex(v1_id)
        v2=self.get_vertex(v2_id)
        if v2_id not in v1.get_neighbors():
            v1.add_neigbor(v2)
        if v1_id not in v2.get_neighbors():
            v2.add_neigbor(v1)
    def get_vertices(self):
        return [v.id for v in self.vertices.keys()]

我也在使用一个测试 class，里面有 bfs 算法：

from graph_object import *


def bfs(g, s):
    explored, queue = [], [s]
    while queue:
        current_vertex = queue.pop(0)
        if current_vertex not in explored:
            explored.append(current_vertex)
            neighbors = g[current_vertex]
            queue += neighbors
    return explored


graph = Graph()

graph.add_edge('a', 'b')
graph.add_edge('b', 'c')
graph.add_edge('c', 'd')
graph.add_edge('d', 'b')
graph.add_edge('d', 'g')

print("List of vertex IDs in graph:")
vertices = graph.get_vertices() #returns graph vertices as a list of vertex IDs
print(vertices)

vertices_dict = graph.vertices
print("Vertex information in format <vertex id>:<list of neighbors>")
for vertex in vertices_dict.keys():
    print(vertex)


print("BFS(a) explored the elements in graph in the order:")
print(*bfs(graph, 'a'), sep=', ')

当我运行代码时，我得到这个错误：

Traceback (most recent call last):
List of vertex IDs in graph:
File "C:/Users/rawsly/PycharmProjects/MiniProject/test.py", line 40, in <module>
['a', 'b', 'c', 'd', 'g']
print(*bfs(graph, 'a'), sep=', ')
Vertex information in format <vertex id>:<list of neighbors>
File "C:/Users/rawsly/PycharmProjects/MiniProject/test.py", line 10, in bfs
a:['b']
neighbors = g[current_vertex]
b:['a', 'c', 'd']
TypeError: 'Graph' object is not subscriptable

我知道在 bfs 中为 explored 使用 set 结构更好，但后来我意识到输出没有排序，因为 set 结构未排序。因此我想改用 list 。另一方面，使用 dequeue 也更有效率，但现在我没有考虑效率。我稍后会改进代码，但首先，我想解决这个错误。

Answer 1

您访问图表的方式有误。它不是字典，所以它不知道如何按照您现在编码的方式获取项目。您还将运行遇到队列问题，因为这不是您将项目添加到列表的方式。您有一个 getter 用于图表中的顶点 class 您可以使用并添加到队列列表中您可以使用追加。

def bfs(g, s):
    explored, queue = [], [s]
    while queue:
        current_vertex = queue.pop(0)
        print(current_vertex)
        if current_vertex not in explored:
            explored.append(current_vertex)
            neighbors = g.get_vertex(current_vertex).get_neighbors()
            queue.extend(neighbors)
    return explored

已编辑：我看到您想扩展队列而不是追加。您还想使用 get_neighbors 函数以及获取顶点。

Answer 2

替换

neighbors = g[current_vertex]

和

neighbors = g.get_vertex(current_vertex).get_neighbors()

Python - Type Error: 'Graph' object is not subscriptable

Python - Type Error: 'Graph' object is not subscriptable

graph-theory

breadth-first-search