Question

Write a Java program that implements the Depth-First Search (DFS) algorithm.

Input format: This is a sample input from a user.

3 2 0 1 1 2

The first line (= 3 in the example) indicates that there are three vertices in the graph. You can assume that the first vertex starts from the number 0. The second line (= 2 in the example) represents the number of edges, and following two lines are the edge information. This is the graph with the input information.

Sample Run 0: Assume that the user typed the following lines

3

2

0 1

1 2

This is the correct output. Your program should display the mark array of DFS. For the problem, you can assume that the starting vertex is always 0. And also, you can assume that the graph is connected.

Mark[0]:1

Mark[1]:2

Mark[2]:3

Sample Run 1: Assume that the user typed the following lines

5

6

0 1

0 2

0 3

1 3

2 3

3 4

This is the correct output.

Mark[0]:1

Mark[1]:2

Mark[2]:5

Mark[3]:3

Mark[4]:4

Sample Run 2: Assume that the user typed the following lines

5

6

0 1

0 2

0 3

1 4

2 3

3 4

This is the correct output.

Mark[0]:1

Mark[1]:2

Mark[2]:4

Mark[3]:5

Mark[4]:3

Answer 1

// GraphDFS.java

import java.util.Scanner;

public class GraphDFS {
  
   private int n; // number of vertices
   private int data[][]; // adjacency matrix to represent the graph status
   private int mark[]; // array to store the order of visiting the vertices using DFS
   private int currentMark; // counter to store the current visitation number
  
   // constructor
   public GraphDFS(int n)
   {
       this.n = n;
       data = new int[n][]; // create data array of n rows
      
       mark = new int[n]; // create mark array of n rows
      
       // loop to set all entries of mark to 0 and data to 0
       for(int i=0;i<n;i++)
       {  
           mark[i] = 0;
           data[i] = new int[n]; // create n columns for ith row
           for(int j=0;j<n;j++)
               data[i][j] = 0;
       }
       currentMark = 0; // initialize currentMark to 0
   }
  
   // method to add an edge from ith node to jth node
   public void addEgde(int i, int j)
   {
       data[i][j] =1;
   }
  
   // method to implement Depth-First Search (DFS) algorithm starting from vertex 0
   public void DFS()
   {
       DFS(0);       // call the helper recursive method
      
       // loop to display the order in which the vertices was visited
       for(int i=0;i<n;i++)
           System.out.println("Mark["+i+"]:"+mark[i]);
   }
  
   //helper method to implement DFS traversal
   private void DFS(int src)
   {
       // src has been visited
       currentMark++; // increment currentMark
       mark[src]=currentMark; // set src entry of mark to currentMark
      
       // loop to determine the unvisited neighbors of src and perform DFS
       for(int i=0;i<data[src].length;i++)
       {
           // ith vertex is a neighbor and not visited yet, call DFS for vertex i
           if((data[src][i] == 1) && (mark[i] == 0))
               DFS(i);
       }
   }
  
   public static void main(String[] args) {
  
       GraphDFS g;
       Scanner scan = new Scanner(System.in);
       int numVertices, numEdges, startV, endV;
       // input number of vertices
       numVertices = scan.nextInt();
      
       // input number of edges
       numEdges = scan.nextInt();
      
       // create a graph for numVertices
       g = new GraphDFS(numVertices);
      
       // loop to input and add input edge to the graph
       for(int i=0;i<numEdges;i++)
       {
           startV = scan.nextInt();
           endV = scan.nextInt();
           g.addEgde(startV, endV);
       }
      
       // perform DFS
       g.DFS();
  
   }

}

// end of GraphDFS.java

Output: