Question

Help !! I need help with Depth-First Search using an undirected graph.

Write a program, IN JAVA, to implement the depth-first search algorithm using the pseudocode given.

Write a driver program, which reads input file mediumG.txt as an undirected graph and runs

the depth-first search algorithm to find paths to all the other vertices considering 0 as the

source. This driver program should display the paths in the following manner:

0 to ‘v’: list of all the vertices traversed to go to v from 0, separated by ‘,’ . There is another

file called tinyG.txt which you can use for your testing purpose.

DFS(G) 1 for each vertex u E G.V 2 u.colorWHITE 4 time=0 5 for each vertex u E G. V 6 if u.color WHITE DFS-VISIT (G, u) DFS-VISIT(G, u) 1 timetime 1 2 u.dtime 3 u.color= GRAY 4 for each v E G.Adilu] II white vertex u has just been discovered Il explore edge (u, v) if v. color == WHITE DFS-VISIT (G, v) 8 u. color= BLACK 9 time= time+1 I/ blacken u; it is finished 10 u,f=time

Graph.java

import java.io.BufferedReader;

import java.io.IOException;

import java.util.Arrays;

import java.util.LinkedList;

import java.util.StringTokenizer;

/**

* This is a super class represents a graph.

*/

public class Graph {

public int V; // the number of vertex of tihs graph

public int E; // the number of edges of this graph

public LinkedList<Integer>[] adj; // the list to store the adjacent

vertices

/**

* Constructor, initiate V and E to 0.

*/

public Graph()

{

V = 0;

E = 0;

}

/**

* Constructor, read from a file and construct a new graph

* @param reader the file buffer reader

* @throws IOException

*/

public Graph(BufferedReader reader) throws IOException

{

String line;

line = reader.readLine();

V = Integer.parseInt(line);

line = reader.readLine();

E = Integer.parseInt(line);

adj = new LinkedList[V];

for (int v = 0; v < V; v++) {

adj[v] = new LinkedList<Integer>();

}

while ((line = reader.readLine()) != null) {

int tempV1, tempV2;

StringTokenizer st = new StringTokenizer(line, " ");

tempV1 = Integer.parseInt(st.nextToken());

tempV2 = Integer.parseInt(st.nextToken());

addEdge(tempV1, tempV2);

}

}

/**

* add an edge to the graph

* @param v one vertex of an edge

* @param w the other vertex of an edge

*/

public void addEdge(int v, int w) {

}

/**

* Convert the graph to string.

* @return a string represents the adjacent list of this graph

*/

public String toString()

{

String s = new String();

s = "There are "+V+" vertices and "+E+" edges\n";

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

{

s = s+i+": ";

for(int j = 0; j<adj[i].size();j++)

{

s = s+adj[i].get(j)+" ";

}

s = s+"\n";

}

return s;

}

}

TinyDG.txt

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

Answer 1

• Points to be taken care of :

1. i just used the data that is provided in TinyDG.txt. if you have to use any other file please change the file name in the code.
2. If you provide any wrong destination , that is there is no any path from that source 0 to your given destination then program will give output as "No path found from source 0 to destination" else it will display the comma separated traversed node form source 0 to given destination.
3. In my code i am using destination as 5 , you can test it with any destination by just changing the value of destination in the code DFS(graphObject.adj,5) , here 5 is the destination
4. i just include "DFSTraversal" class which is responsible for all the DFS operation.

• code ;
• --------

import java.io.BufferedReader;
import java.io.IOException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

/**
* This is a super class represents a graph.
*/

public class Graph {
public int V; // the number of vertex of tihs graph
public int E; // the number of edges of this graph
public LinkedList<Integer>[] adj; // the list to store the adjacent vertices

/**
* Constructor, initiate V and E to 0.
*/
public Graph()
{
V = 0;
E = 0;
}
  
/**
* Constructor, read from a file and construct a new graph
* @param reader the file buffer reader
* @throws IOException
*/
public Graph(BufferedReader reader) throws IOException
{
String line;
line = reader.readLine();
V = Integer.parseInt(line);
line = reader.readLine();
E = Integer.parseInt(line);
adj = new LinkedList[V];
for (int v = 0; v < V; v++)
{
adj[v] = new LinkedList<Integer>();
}
while ((line = reader.readLine()) != null)
{
int tempV1, tempV2;
StringTokenizer st = new StringTokenizer(line, " ");
tempV1 = Integer.parseInt(st.nextToken());
tempV2 = Integer.parseInt(st.nextToken());
addEdge(tempV1, tempV2);
}
}

/**
* add an edge to the graph
* @param v one vertex of an edge
* @param w the other vertex of an edge
*/
public void addEdge(int v, int w) {
this.adj[v].add(w);
}

/**
* Convert the graph to string.
* @return a string represents the adjacent list of this graph
*/
public String toString()
{
String s = new String();
s = "There are "+V+" vertices and "+E+" edges\n";
for(int i=0;i<V;i++)
{
s = s+i+": ";
for(int j = 0; j<adj[i].size();j++)
{
s = s+adj[i].get(j)+" ";
}
s = s+"\n";
}
return s;
}
  
}
class DFSTraversal
{
static String NodeColour[];
static String visitedNode =""; // variable that track the list of visited node from source to destrination
static boolean reachedDestination = false;
public static void DFS( LinkedList<Integer> G[] , int destination)
{
int size = G.length; // getting the number of vertices
NodeColour = new String[size];
// initialising the coulur of node to WHITE initially
for( int i=0;i<size;i++)
{
NodeColour[i] = "WHITE";
}
System.out.println("Below is the list of node traversed from source 0 to destination "+ destination);
  
DFSVisit(G,0,destination);
if(!reachedDestination)
System.out.println(" \nNo path found from source 0 to destination "+ destination);
else
System.out.print( "0 to \'"+destination+"\' : "+visitedNode);
}
public static void DFSVisit(LinkedList<Integer> G[] , int node, int destination)
{
// if visited node is our destination then return from function , do nothing
if (node == destination)
{

visitedNode = visitedNode.concat(node+",");
reachedDestination = true;
return;
}
NodeColour[node] = "GRAY"; // maing colour of visited node to GRAY
visitedNode = visitedNode.concat(node+",");

// traverse each adjacent node of visited node
LinkedList<Integer> list = G[node];
for(int v : list)
{
if (NodeColour[v].equals("WHITE"))
{
DFSVisit(G , v,destination);
}
}
// make colour of processed node to BLACK
NodeColour[node] = "BLACK";
  
}
public static void main(String args[]) throws Exception
{
// reading data from TinyDG.txt
BufferedReader br = new BufferedReader(new FileReader("TinyDG.txt"));
Graph graphObject = new Graph(br);
System.out.println(graphObject.toString());
// traverse the node from source 0 to destination 5
DFS(graphObject.adj,5);
}
}

• output of the screenshot

C: \Userslabhayk3x Desktop>java DFSTraversal There are 13 vertices and 22 edges 2: 3 0 3: 2 5 4: 2 3 6: 0 849 7: 9 6 9: 10 11 10: 12 11: 12 4 12: 9 Below is the list of node traversed from source 0 to destination 5 0 to '5' 0,1,5, C: \Userslabhayk3x\Desktop>