Depth First Search(DFS) for a graph in Java

Depth First Search (DFS) is a graph traversal algorithm used to explore nodes and edges in a graph. In Java, DFS starts at a selected vertex and explores as far as possible along each branch before backtracking. It employs a stack or recursion to keep track of the vertices that need to be visited next.

Implementation of DFS for a graph

Graph Representation: The graph can be represented using adjacency lists, where each vertex stores a list of its adjacent vertices.

Traversal Algorithm: Implement a recursive or use a stack to perform the DFS traversal. The function should visit each vertex and recursively visit its adjacent vertices until all vertices are visited.

Visited Marking: Maintain a boolean array or set to keep track of visited vertices to avoid revisiting them during traversal.

Start Vertex: Choose a starting vertex from which to begin the traversal. Typically, DFS can be started from any vertex in the graph.

Traversal Path: Record the order in which vertices are visited to obtain the traversal path.

Java program for DFS  of a Graph

import java.util.*;
class Graph {
  private int V; // number of vertices
  private LinkedList<Integer> adj[]; // Adjacency list representation
  Graph(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
        adj[i] = new LinkedList();
  }
  void addEdge(int v, int w) {
     adj[v].add(w);
  }
  void DFSUtil(int v, boolean visited[]) {
     visited[v] = true;
     System.out.println(v + " ");
     Iterator<Integer> i = adj[v].listIterator();
     while (i.hasNext()) {
         int n = i.next();
         if (!visited[n])
             DFSUtil(n, visited);
      }
   }
   void DFS(int v) {
       boolean visited[] = new boolean[V];
       DFSUtil(v, visited);
    }
    public static void main(String args[]) {
       Graph graph = new Graph(5);
       graph.addEdge(0, 1);
       graph.addEdge(0, 2);
       graph.addEdge(1, 2);
       graph.addEdge(1, 4);
       graph.addEdge(2, 0);
       graph.addEdge(2, 3);
       graph.addEdge(3, 4);
       graph.addEdge(4, 4);
       System.out.println("Following is Depth First Traversal (starting from vertex 1):");
       graph.DFS(1);
     }
}

Output:

Following is Depth First Traversal (starting from vertex 1):

1 2 0 3 4