我正在尝试实施广度优先搜索

Question

我正在尝试有一个程序，允许用户点击一个顶点选择开始顶点和悬停在一个顶点选择结束顶点。然后程序使用广度优先搜索来选择路径。我无法创建路径，因为每当我选择两个顶点时，都会得到一个none类型。请帮忙。你知道吗

    from collections import deque
from load_graph import load_graph

vertex_dict = load_graph("graph.txt")


def bfs(start, goal):
    backpointers = {}
    path = []
    q = deque()
    q.append(start)
    backpointers[start] = None
    while len(q) >= 1:
        x = q.popleft()
        if x == goal:
            path.append(goal)
            while backpointers[x] != None:
                print(backpointers)
                path.append(backpointers[x])
                x = backpointers[x]
            return path
        else:
            for vertex in x.get_adjacent():
                vertex = vertex_dict[vertex.strip()]
                if vertex not in backpointers:
                    backpointers[vertex] = x
                    q.append(vertex)
                    print(len(x.get_adjacent()))

我肯定这个问题在这里，因为它返回一个无类型，当我把一堆打印语句，它在其他部分卡住了。 This is what it looks likes

顶点类：

from cs1lib import *
class Vertex:

    def __init__(self, name, adjacent, x, y):
        self.name = name
        self.adjacent = adjacent.split(",")
        self.adjacentSTR = adjacent
        self.x = int(x)
        self.y = int(y)
        self.r = 10
        self.distance = None
        self.is_red = False

    def __str__(self):
        return self.name+"; "+"Adjencent Vertices: "+self.adjacentSTR+" Location: "+str(self.x)+", "+ str(self.y)

    def get_x(self):
        return self.x

    def set_distance(self, d):
        self.distance = d

    def get_vertex(self):
        return self

    def get_y(self):
        return self.y

    def get_adjacent(self):
        return self.adjacent

    def link(self, vertex, r, g, b):
        set_fill_color(r, g, b)
        set_stroke_width(2)
        set_stroke_color(r, g, b)
        draw_line(self.x, self.y, vertex.get_x(), vertex.get_y())

    def draw(self, r, g, b):
        set_fill_color(r, g, b)
        set_stroke_width(1)
        draw_circle(self.x, self.y, self.r)

    def mouse_is_nearby(self, mx, my):
        if mx <= self.x + self.r  and mx >= self.x - self.r and my <= self.y + self.r and my >= self.y - self.r:
           # print("close to: " +self.name)
            return True

Answer 1

试试这个：

from collections import deque

def path(back_links, goal):
    path = [goal]
    node = goal
    while back_links[node] is not None:
        node = back_links[node]
        path = [node] + path
    return path

def bfs(start, goal):
    q = deque([start])
    visited, back_links = set([]), {start.name: None}
    while q:
        node = q.popleft()
        visited.add(node.name)
        if node.name == goal.name:
            return path(back_links, goal.name)
        for neighbor in node.get_adjacent():
            if neighbor.name in visited:
                continue
            q.append(neighbor)
            back_links[neighbor.name] = node.name
    return []