How to implement the DFS of a graph import java.util.Arrays; import java.util.Sc

ID: 3804468 • Letter: H

Question

How to implement the DFS of a graph

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;
import java.io.File;

public class DFS{

   /* DFS(G)
   Given an adjacency matrix describing a graph, print the
   listing of vertices encountered by a depth-first search starting at
   vertex 0.
   */
   public static void DFS(int[][] G){
       int n = G.length;

       /* ... Your code here ... */

   }


   /* main()
   Contains code to test the DFS method.
   */
   public static void main(String[] args){
       Scanner s;
       if (args.length > 0){
           try{
               s = new Scanner(new File(args[0]));
           } catch(java.io.FileNotFoundException e){
               System.out.printf("Unable to open %s ",args[0]);
               return;
           }
           System.out.printf("Reading input values from %s. ",args[0]);
       }else{
           s = new Scanner(System.in);
           System.out.printf("Reading input values from stdin. ");
       }

       int graphNum = 0;
       double totalTimeSeconds = 0;

       //Read graphs until EOF is encountered (or an error occurs)
       while(true){
           graphNum++;
           if(graphNum != 1 && !s.hasNextInt())
               break;
           System.out.printf("Reading graph %d ",graphNum);
           int n = s.nextInt();
           int[][] G = new int[n][n];
           int valuesRead = 0;
           for (int i = 0; i < n && s.hasNextInt(); i++){
               for (int j = 0; j < n && s.hasNextInt(); j++){
                   G[i][j] = s.nextInt();
                   valuesRead++;
               }
           }
           if (valuesRead < n*n){
               System.out.printf("Adjacency matrix for graph %d contains too few values. ",graphNum);
               break;
           }
           long startTime = System.currentTimeMillis();
           DFS(G.clone());
           long endTime = System.currentTimeMillis();
           totalTimeSeconds += (endTime-startTime)/1000.0;

       }
       graphNum--;
       System.out.printf("Processed %d graph%s. Average Time (seconds): %.2f ",graphNum,(graphNum != 1)?"s":"",(graphNum>0)?totalTimeSeconds/graphNum:0);
   }
}

Explanation / Answer

// Java program to print DFS traversal from a given given graph

import java.io.*;

import java.util.*;

// This class represents a directed graph using adjacency list

// representation

class Graph

{

private int V; // No. of vertices

// Array of lists for Adjacency List Representation

private LinkedList<Integer> adj[];

// Constructor

Graph(int v)

{

V = v;

adj = new LinkedList[v];

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

adj[i] = new LinkedList();

}

//Function to add an edge into the graph

void addEdge(int v, int w)

{

adj[v].add(w); // Add w to v's list.

}

// A function used by DFS

void DFSUtil(int v,boolean visited[])

{

// Mark the current node as visited and print it

visited[v] = true;

System.out.print(v+" ");

// Recur for all the vertices adjacent to this vertex

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

while (i.hasNext())

{

int n = i.next();

if (!visited[n])

DFSUtil(n, visited);

}

// The function to do DFS traversal. It uses recursive DFSUtil()

void DFS(int v)

{

// Mark all the vertices as not visited(set as

// false by default in java)

boolean visited[] = new boolean[V];

// Call the recursive helper function to print DFS traversal

DFSUtil(v, visited);

}

public static void main(String args[])

{

Graph g = new Graph(4);

g.addEdge(0, 1);

g.addEdge(0, 2);

g.addEdge(1, 2);

g.addEdge(2, 0);

g.addEdge(2, 3);

g.addEdge(3, 3);

System.out.println("Following is Depth First Traversal "+

"(starting from vertex 2)");

g.DFS(2);

}