Где я могу определить очередь и как мне загрузить BFS в коде? - PullRequest
Новая
       58

Где я могу определить очередь и как мне загрузить BFS в коде?

0 голосов
/ 28 апреля 2019

У меня есть код для выполнения поиска в ширину на графике, и я попытался вызвать процедуру BFS (например, BFS (graph, "A", "C"), однако она показывает мне ошибку. Мне нужноопределить MyQUEUE, как и где именно это определить?

Я пытался создать очередь классов и определить ее, однако она продолжает показывать мне ошибку 

def BFS(graph,start,end):
  q = MyQUEUE() # make an empty queue first
  q.enqueue([start]) # add the start node onto the queue
  while q.IsEmpty() == False:
       path = q.dequeue()
       last_node = path[len(path)-1]
       print (path)
       if last_node == end:
           print ("VALID_PATH : ", path)
       for link_node in graph[last_node]:
           if link_node not in path:
                new_path = []
                new_path = path + [link_node]
                q.enqueue(new_path)

graph = {'A': ['B', 'C','E'],
 'B': ['A','C', 'D'],
 'C': ['D'],
 'D': ['C'],
 'E': ['F','D'],
 'F': ['C']}

Я ожидаю, что вызовет BFS воболочка (BFS (graph, node1, node2) работает правильно, поэтому она находит все доступные трейлы.

1 Ответ

0 голосов
/ 28 апреля 2019

Python предоставляет структуру данных очереди как часть своего модуля collections (он называется, несколько странно, deque).Что касается вашей ситуации, вы бы использовали append() для enqueue и popleft() для dequeue (или appendleft() и pop()).

Тем не менее, если бы я реализовывал простой класс FIFO MyQUEUE для ваших простых спецификаций, используя простой список, это выглядело бы примерно так: 

class MyQUEUE:
    def __init__(self):
        self.queue = []  # start with an empty list

    def enqueue(self, elem):
        self.queue.append(elem)  # add element to back of list

    def dequeue(self):
        return self.queue.pop(0)  # remove element from front of list
...