In Java implement the necessary methods in DepthFirstSearch.java to implement a depth first search of a graph:

import java.util.*;

public class DepthFirstSearch {

// Class to represent a graph using adjacency list

// and the number of nodes

static class Graph {

int Nodes;

LinkedList adjVertices[];

int[][] adjMatrix;

@SuppressWarnings("unchecked")

public Graph(int n) {

this.Nodes = n;

adjVertices = new LinkedList[Nodes];

adjMatrix = new int[Nodes][Nodes];

for (int i = 0; i < Nodes; i++) {

adjVertices[i] = new LinkedList();

}

}

}

// Add an edge between two given vertices

static void addEdge(Graph graph, int src, int dst) {

graph.adjVertices[src].addFirst(dst);

graph.adjVertices[dst].addFirst(src);

}

// Create the adjacency matrix representation

static void generateMatrix(Graph graph) {

}

// print the adjacency matrix

static void printMatrix(Graph graph) {

}

// Print the graph as adjacency list

static void printGraph(Graph graph) {

}

static void BFS(Graph graph, int s) {

}

// prints all not yet visited vertices reachable from start

static void DFS(Graph graph, int start) {

// Initially mark all vertices as not visited

// Create a stack for DFS

// Push the current source node

// Pop a vertex from stack and print it

// Stack may contain same vertex twice. So

// we need to print the popped item only

// if it is not visited.

// Get all adjacent vertices of the popped vertex s

// If a adjacent has not been visited, then push it

// to the stack.

}

// Driver program to test methods of graph class

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.println("How many vertices?: ");

int nodeCount = input.nextInt();

Graph graph = null;

if (nodeCount > 0) {

graph = new Graph(nodeCount);

}

System.out

.println("Enter the edges between two nodes(counting from 0), -1 to stop");

while (true) {

int src = input.nextInt();

if (src == -1)

break;

int dest = input.nextInt();

if ((src > nodeCount - 1) || (dest > nodeCount - 1)) {

System.out.println("Invalid vertex.");

} else {

addEdge(graph, src, dest);

}

}

System.out.println("Enter your choices: "

+ "1 print adjacency list " + "2 print adjacency matrix "

+ "3 print breadth first search "

+ "4 print depth first search ");

int choice = input.nextInt();

int source = 0;

switch (choice) {

case 1:

printGraph(graph);

break;

case 2:

generateMatrix(graph);

printMatrix(graph);

break;

case 3:

System.out.println("Enter the beginning vertex:");

source = input.nextInt();

System.out.println("BFS traversal of the graph starting at "

+ source);

BFS(graph, source);

break;

case 4:

System.out.println("Enter the beginning vertex:");

source = input.nextInt();

System.out.println("DFS traversal of the graph starting at "

+ source);

DFS(graph, source);

break;

}

input.close();

}

}