Question

in Java

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

Answer 1

// import the necessary package

import java.util.*;

// declare the class graph.

public class Graph

{

// Declare the variable.

private static int V;

private static LinkedList<Integer> adj[];

// Constructor of the class

Graph(int v)

{

// Assign value

V = v;

// Declare linklist

adj = new LinkedList[v];

// Start the for loop

for (int i = 0; i < v; ++i)

// create new linklist.

adj[i] = new LinkedList();

}

// definition of the method

void addEdge(int v, int w)

{

// adding edge to graph

adj[v].add(w);

}

// Definition of the method

public static void dfsPrintTrace(Graph g)

{

// Declare an boolean array.

boolean marked[] = new boolean[V];

//display the statement on console.

System.out.println("Starting from vertex 0");

// start the for loop.

for (int i = 0; i < V; ++i)

// check whether the value in array

// is false or not.

if (marked[i] == false)

// Call to the method

dfsPrintTrace(g, 0, marked, 0);

}

// definition of the method

private static void dfsPrintTrace(Graph g, int start,

boolean[] marked, int indent)

{

// declare variable

int n=0;

// set the value of the starting

// value of array to be true.

marked[start] = true;

// traversing the graph

Iterator<Integer> i = adj[start].listIterator();

// Start the while loop

while (i.hasNext())

{

// set the value of n.

n = i.next();

if (!marked[n])

{

// display the statement on console.

System.out.println(

"First time at vertex " + n);

// call to the method.

dfsPrintTrace(g, n, marked, indent++);

}

else

{

// Display the statement on console.

System.out.println(

"Visiting vertex " + n + " again");

}

}

// display the statement on console.

System.out.println(

"Finished searching from " + n);

}

// start the main method.

public static void main(String args[])

{

// declare the object of graph

Graph g = new Graph(4);

// Add edges to graph.

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

// Display the statement on console.

System.out.println("Depth First Traversal");

// Call to the method.

g.dfsPrintTrace(g);

}

}

Answer 2

// import the necessary package

import java.util.*;

// declare the class graph.

public class Graph

{

// Declare the variable.

private static int V;

private static LinkedList<Integer> adj[];

// Constructor of the class

Graph(int v)

{

// Assign value

V = v;

// Declare linklist

adj = new LinkedList[v];

// Start the for loop

for (int i = 0; i < v; ++i)

// create new linklist.

adj[i] = new LinkedList();

}

// definition of the method

void addEdge(int v, int w)

{

// adding edge to graph

adj[v].add(w);

}

// Definition of the method

public static void dfsPrintTrace(Graph g)

{

// Declare an boolean array.

boolean marked[] = new boolean[V];

//display the statement on console.

System.out.println("Starting from vertex 0");

// start the for loop.

for (int i = 0; i < V; ++i)

// check whether the value in array

// is false or not.

if (marked[i] == false)

// Call to the method

dfsPrintTrace(g, 0, marked, 0);

}

// definition of the method

private static void dfsPrintTrace(Graph g, int start,

boolean[] marked, int indent)

{

// declare variable

int n=0;

// set the value of the starting

// value of array to be true.

marked[start] = true;

// traversing the graph

Iterator<Integer> i = adj[start].listIterator();

// Start the while loop

while (i.hasNext())

{

// set the value of n.

n = i.next();

if (!marked[n])

{

// display the statement on console.

System.out.println(

"First time at vertex " + n);

// call to the method.

dfsPrintTrace(g, n, marked, indent++);

}

else

{

// Display the statement on console.

System.out.println(

"Visiting vertex " + n + " again");

}

}

// display the statement on console.

System.out.println(

"Finished searching from " + n);

}

// start the main method.

public static void main(String args[])

{

// declare the object of graph

Graph g = new Graph(4);

// Add edges to graph.

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

// Display the statement on console.

System.out.println("Depth First Traversal");

// Call to the method.

g.dfsPrintTrace(g);

}

}