Write a program DFSTrace that contains a version of a depth first search that prints a trace of its traversal. Write a public static method:

public static void dfsPrintTrace(Graph g) { // *** Declare and initialize the marked array. dfsPrintTrace(g, 0, marked, 0); } 

This method calls a private method:

private static void dfsPrintTrace(Graph g, int start, boolean[] marked, int indent) 

All references to a method below refer to this second method. Every message printed should be preceded by the number of spaces specified by the indent parameter. A recursive call should pass an indent value with 1 added.

The first time the method visits a vertex, it should print the message "First time at vertex n", where n is the integer label of the vertex.

Every other time it visits a vertex, it should print the message "Visiting vertex n again".

When it exits, it should print the message "Finished searching from n".

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

First visit to 0. First visit to 6. Visited 0 again. First visit to 4. First visit to 5. First visit to 3. Visited 5 again. Visited 4 again. Finished with 3. Visited 4 again. Visited 0 again. Finished with 5. Visited 6 again. Visited 3 again. Finished with 4. Finished with 6. First visit to 2. Visited 0 again. Finished with 2. First visit to 1. Visited 0 again. Finished with 1. Visited 5 again. Finished with 0. 

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); dfsPrintTrace(g); } 

Include in the comments of your code the answer to this question: What is the pattern formed by the "First visit" and "Finished" messages?

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