我正在尝试实施广度优先搜索
I am trying to implement breadth first search
我正在尝试创建一个程序,允许用户单击顶点以选择起始顶点并将鼠标悬停在顶点上以选择 end_vertex。然后程序使用广度优先搜索来选择路径。我无法创建路径,因为每当我选择两个顶点时,我都会得到一个 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()))
我肯定问题在这里,因为它 returns 是 none 类型,当我输入一堆打印语句时,它卡在了 else 部分。
This is what it looks likes
顶点Class:
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 []
我正在尝试创建一个程序,允许用户单击顶点以选择起始顶点并将鼠标悬停在顶点上以选择 end_vertex。然后程序使用广度优先搜索来选择路径。我无法创建路径,因为每当我选择两个顶点时,我都会得到一个 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()))
我肯定问题在这里,因为它 returns 是 none 类型,当我输入一堆打印语句时,它卡在了 else 部分。 This is what it looks likes
顶点Class:
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 []