In this assignment, you are required to implement an array-based queue and the breadth first search
algorithm. You are required to read reference materials to learn how to implement them based on the
foundational knowledge you acquired in this course.
Part 1: Array-Based Queue (60%)
The first part of this assignment is to implement a queue based on a fixed-length array. The fixedlength
array is implemented based on the Array class in the file assignlib.py. Your array-based
queue should meet the following requirements:
1. The queue should use the provided Array class to hold its items. It should not use any
other collections such as list to do so. You should also access the stored items in Array through
its instance methods. Failure to do so may result in zero mark for this part.
2. The class that implements the queue should be named ArrayQueue.
3. An integer should be used to indicate the capacity of the queue (i.e. the maximum number of
items that the queue can hold) when the queue is being created.
4. It has an instance method named is_empty that returns a boolean value to indicate whether the
queue is empty or not.
5. It has an instance method named enqueue that accepts an item as its parameter and implement
the typical enqueue operation of a queue. The method should print Error: The queue is
full! if the queue has reached its maximum capacity.
6. It has an instance method named dequeue that returns an item and implements the typical
dequeue operation of a queue. The method should print Error: The queue is empty! if the
queue does not contain any item.
7. It has an instance method named to_list that returns the item held by the queue as a list
object.
Remarks: You may refer to Chapter 5 (Pages 148–151) of Stephens (2019) for more information. In
particular, you may need to handle the case after the number of items that have been enqueued and
dequeued has reached the capacity.
Part 2: Breadth-First Search (40%)
Given a directed graph such as the one shown below, the breadth-first search can be used to determine
whether a target node can be reached from a source node, i.e. there is a path from the source node
to the target node. For example, in the graph below, node a is reachable from node b but not the
opposite.
To represent a graph, one can uses a node object similar to the one below. The Node objects is similar
to those used in linked lists. A Node object holds its value (name) and links to its neighbouring nodes. Unlike those in linked list, each node can have more than one neighbouring nodes. The code
below shows also the nodes in the aforementioned figure.
In this part, you should implement a method that checks whether a target node is reachable from the
source node with the following requirements:
1. The search method should be named bfs. It should accept two parameters, indicating the source
node and target node, respectively. The method should return True if the target node is reachable
from the source node, and False otherwise.
2. The search method should be based on the breadth-first algorithm. Specifically, it should explore
all nodes that have the same distance from the source node before exploring nodes that have a
longer distance from the source node.
3. The search method should be able to handle directed graph with cycles. For example, it should
be able to handle the cycle a →d→ e→a in the example graph.
Remarks: You may refer to Chapter 6 of Bhargava (2016) and the Breadth-First Search entry in
Wikipedia1 for more information.