HW15: BFS Back-End

Create a new class that implements the Queue interface. If you do an array-based implementation, name your class ArrayQueueImplementation; if you do a link-based one, name it LinkedQueueImplementation. You're free to choose any of the four implementations we talked about in class: circular array, linear linked, circular linked, or two-part circular linked.

Include in your class a main method that carefully tests all the ADT behaviors. You may (and should) write this method first, just using the mystery queue implementation at first to verify that your tests are correct.

In a file called QueueDemo.java, write a program that uses your Queue implementation to perform breadth-first search on a variety of hard-coded graphs.

You may do something as simple as print out the node IDs of the nodes that you visit, or something fancier, or you may recycle your code from part 1 of Homework 6, where you used BFS to label a connected component. Regardless, your program should print out some kind of sensible output that allows a user (the grader) to easily verify that you're performing a breadth-first search (provided that she can read your source code to see how each graph was constructed).

(Note that DFS can also label a whole connected component, so if you just print out the labels that BFS produces, make sure to include some explanatory output that explains why your output demonstrates that your BFS implementation works properly.)

Write five test graphs, and make sure to test weird cases as well as normal ones.

To do this part, you'll probably want to download all the mystery unweighted graph implementation files from the code directory.