1. Introduction

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack (implicit or explicit) to achieve this.

2. Program Steps

1. Start from the source vertex.

2. Visit the vertex and mark it as visited.

3. Recursively visit all the adjacent unvisited vertices.

4. If no adjacent vertex is found, backtrack to the previous vertex.

3. Code Program

import java.util.*;

public class DFS {

    private int V;   // No. of vertices
    private LinkedList<Integer> adjList[]; //Adjacency Lists

    // Constructor
    DFS(int v) {
        V = v;
        adjList = new LinkedList[v];
        for (int i=0; i<v; ++i) {
            adjList[i] = new LinkedList();
        }
    }

    // Function to add an edge into the graph
    void addEdge(int v,int w) {
        adjList[v].add(w);
    }

    // DFS traversal starting from a given vertex
    void traverse(int s, boolean visited[]) {
        visited[s] = true;
        System.out.print(s + " ");

        Iterator<Integer> i = adjList[s].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n]) {
                traverse(n, visited);
            }
        }
    }

    void traverse(int s) {
        boolean visited[] = new boolean[V];
        traverse(s, visited);
    }

    public static void main(String args[]) {
        DFS g = new DFS(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("Depth First Traversal starting from vertex 2:");

        g.traverse(2);
    }
}

Output:

Depth First Traversal starting from vertex 2:
2 0 1 3

4. Step By Step Explanation

1. DFS: Main class that represents a directed graph using adjacency list representation.

2. DFS(int v): Constructor to initialize the graph with the specified number of vertices.

3. addEdge(int v, int w): Function to add an edge to the graph.

4. traverse(int s, boolean visited[]): Recursive method implementing DFS traversal. It takes a vertex s and a visited array to keep track of visited nodes.

5. The method first marks the node as visited, prints it, and then recursively visits all unvisited neighbors.

6. The traverse(int s) method is an overloaded method that initializes the visited array and starts the DFS traversal.

7. The main method creates a graph, adds edges, and then calls the traverse method to print the DFS traversal starting from vertex 2.

The time complexity of the DFS algorithm is O(V+E) where V is the number of vertices in the graph and E is the number of edges.