使用队列阵列进行广度优先搜索

Question

我正在尝试使用队列数组实现广度优先搜索。我已经为队列数据结构的数组实现运行了测试用例，它们正在按预期工作。

当我将这个队列数组导入广度优先搜索时，执行它会得到一个KeyError: None。但就功能而言，它似乎是正确的。

队列阵列实现：

class QueueArray:
"""
First in first out (FIFO) array implemented using list.
"""
def __init__(self):
self.capacity = 65536
self.data = [None] * self.capacity
self.head = -1
self.tail = -1
def is_empty(self):
"""Return true if the size of the queue is zero."""
if self.head == -1:
return True
return False
def enqueue(self, element):
"""Insert item to the end of the queue."""
if self.head == -1:
self.head += 1
self.tail += 1
self.data[self.tail] = element
def dequeue(self):
"""Remove item from front of the queue."""
if self.is_empty():
raise Exception('Queue underflow!')
queue_front = self.data[self.head]
self.head += 1
return queue_front
def peek(self):
"""Return item at the front of the queue."""
if self.is_empty():
raise Exception('Queue is empty.')
return self.data[self.head]
def size(self):
"""Return size of the queue."""
if self.is_empty():
return 0
return (self.tail - self.head) + 1

使用队列阵列的广度优先搜索：

from queues.queue_array import QueueArray
def breadth_first_search(graph, start):
queue = QueueArray()
queue.enqueue(start)
path = set()
while not queue.is_empty():
vertex = queue.dequeue()
if vertex in path:
continue
path.add(vertex)
for neighbor in graph[vertex]:
queue.enqueue(neighbor)
return path

if __name__ == '__main__':
graph = {
'A' : ['B','S'],
'B' : ['A'],
'C' : ['D','E','F','S'],
'D' : ['C'],
'E' : ['C','H'],
'F' : ['C','G'],
'G' : ['F','S'],
'H' : ['E','G'],
'S' : ['A','C','G']
}
print(breadth_first_search(graph, 'A'))

追溯：

Traceback (most recent call last):
File "graph/bfs.py", line 33, in <module>
print(breadth_first_search(graph, 'A'))
File "graph/bfs.py", line 13, in breadth_first_search
for neighbor in graph[vertex]:
KeyError: None

预期的输出将是一组顶点(由图形关键点组成(，其顺序在每次运行时都不是唯一的。

有人能告诉我如何解决这个问题吗？

Answer 1

您的队列实现存在缺陷。想想当队列中只有一个元素时&那么它就被出列了。is_empty的实施会起作用吗？

头指针在出列之后超出尾指针。这种情况需要处理：

def is_empty(self):
"""Return true if the size of the queue is zero."""
if self.head == -1:
return True
if self.head > self.tail:  # queue was emptied
return True
return False

在这一变化之后，运行BFS会产生：

{'F', 'E', 'G', 'D', 'S', 'H', 'B', 'C', 'A'}