使用队列数组的广度优先搜索

Question

我正在尝试实现 breadth first search using a queue array. I've run test cases for the array implementation of queue 数据结构，它们按预期工作。

当我将这个队列数组导入广度优先搜索时，执行它会得到 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'}

使用队列数组的广度优先搜索

Breadth First Search Using Queue Array

python

algorithm

graph

breadth-first-search