Write a java program BFSTrace that contains a version of a breadth first search that prints a trace. Write a public method with the signature:

public static void bfsPrintTrace(Graph g)

Recall that a breadth first search uses a queue to organize visiting vertices. Print the messages "Enqueueing n" and "Dequeueing n" at the appropriate places.

Here's the output when run on the file data/tinyG.txt:

Enqueued 0.

Dequeued 0.

Enqueued 6.

Enqueued 2.

Enqueued 1.

Enqueued 5.

Dequeued 6.

Enqueued 4.

Dequeued 2.

Dequeued 1.

Dequeued 5.

Enqueued 3.

Dequeued 4.

Dequeued 3.

Here's the main method to insert into your program to test your method(s):

public static void main(String[] args) {

In input = new In("data/tinyG.txt");

Graph g = new Graph(input);

bfsPrintTrace(g);

}

tinyG.txt

13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3