python - 我正在尝试实施广度优先搜索
问题描述
我正在尝试创建一个程序,允许用户单击顶点以选择起始顶点并将鼠标悬停在顶点上以选择 end_vertex。然后程序使用广度优先搜索来选择路径。我无法创建路径,因为每当我选择两个顶点时,我都会得到一个无类型。请帮忙。
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()))
我很肯定它在这里的问题,因为它返回一个无类型,当我放一堆打印语句时,它卡在了 else 部分。 这就是它的样子
顶点类:
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
解决方案
尝试这个:
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 []
推荐阅读
- laravel-5 - 为什么数据值没有传递给控制器?
- jquery - 如何获取select2 JS的默认加载图标
- jupyter-lab - 在 Windows 10 中将 JupyterLab 作为桌面应用程序运行
- node.js - 使用“create-react-app my-app”创建反应应用程序时出错
- c++ - 在 Windows 上打印不起作用
- python - Mercurial Review board UnicodeEncodeError: 'charmap' codec can't encode character u'\ufffd' in position 31: character maps to
- javascript - 如何在 min.js 文件中嵌入 php 代码
- c++ - 为 yaml-cpp 库找到正确的 cmake 配置
- sql - Hive 使用插入覆盖目录时如何创建表?
- conv-neural-network - CNN 中特征图的感受野是重叠的。这有什么影响?