Я пытаюсь осуществить поиск в ширину - PullRequest
Новая
       17

Я пытаюсь осуществить поиск в ширину

0 голосов
/ 05 ноября 2018

Я пытаюсь создать программу, которая позволяет пользователю щелкнуть по вершине, чтобы выбрать начальную вершину, и навести курсор на вершину, чтобы выбрать конечную_вертекс. Затем программа использует поиск в ширину, чтобы выбрать путь. Я не смог создать путь, потому что всякий раз, когда я выбираю обе вершины, я не получаю ни одного типа. Пожалуйста, помогите. 

    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()))

Я уверен, что проблема здесь, потому что он возвращает не тип, и когда я помещаю кучу операторов печати, он застревает в другой части. Вот как это выглядит

Класс вершины: 

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

1 Ответ

0 голосов
/ 05 ноября 2018

Попробуйте это: 

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 []
...