Breadth First Search Using Queue Array

Question

I'm trying to implement breadth first search using a queue array. I've run test cases for the array implementation of queue data structure, and they are working as expected.

When I import this queue array into breadth first search, executing it gives a KeyError: None. But it appears to be correct in terms of functionality.

Queue array implementation:

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

Breadth-first search using queue array:

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:

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

The expected output will be a set of vertices (comprising of the graph keys) whose order will not be unique on every run.

Can someone please let me know how I can fix this?

rdas · Accepted Answer · 2020-11-12 07:15:11Z

2

Your queue implementation is flawed. Think about when there is only one element in the queue & then that is dequeued. Will the is_empty implementation work for that?

The head pointer, goes beyond the tail pointer after the dequeue. That case needs to be handled:

    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

After this change, running the BFS yields:

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

answered Nov 12, 2020 at 7:15

rdas

21.4k6 gold badges39 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Breadth First Search Using Queue Array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related