Flat Preloader Icon

DFS (Depth First Search) algorithm

Depth-First Search (DFS) is a graph traversal algorithm used to explore nodes and edges in a graph by going as deep as possible along each branch before backtracking. It’s often implemented using a stack or recursion.

The basic idea behind DFS is as follows:

  • Choose a starting node and push it onto the stack or start the recursive process.
  • Pop a node from the stack and visit it.
  • Push all of its neighbors onto the stack if they haven’t been visited.
  • Mark the visited node as ‘visited.’
  • Repeat steps 2-4 until the stack is empty or there are no unvisited nodes reachable from the current node.
  • If using recursion, recursively call the function on unvisited neighbors.

Applications Of DFS Algorithm

The Depth-First Search (DFS) algorithm is a fundamental graph traversal algorithm that has various applications in computer science and real-world scenarios. Some of the key applications of DFS include:

  • Topological Sorting: DFS can be used to perform topological sorting on directed acyclic graphs (DAGs), which is useful in scheduling tasks with dependencies.
  • Finding Strongly Connected Components: DFS can be used to find strongly connected components in a directed graph, which is vital in analyzing networks and dependencies.
  • Detecting Cycles: DFS can detect cycles in a graph, which is crucial in tasks such as deadlock detection in operating systems or resource allocation systems.
  • Path Finding: DFS can be used to find a path between two nodes in a graph, which is essential in navigation and routing problems.
  • Maze Generation and Solving: DFS can be used to generate mazes and solve them efficiently.
  • Detecting Connected Components: DFS can be used to find connected components in an undirected graph, helping to identify groups of nodes that are connected to each other.
  • Detecting Bipartite Graphs: DFS can determine whether a graph is bipartite, which has applications in areas such as task scheduling and assignment problems.
  • Network Analysis: DFS is used in the analysis of networks, such as social networks, to identify and analyze communities and connections.
  • Game Theory and Puzzles: DFS can be applied to solve puzzles and analyze game states, such as in chess or other board games.


  • Step 1: SET STATUS = 1 (ready state) for each node in G
  • Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
  • Step 3: Repeat Steps 4 and 5 until STACK is empty
  • Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
  • Step 5: Push on the stack all the neighbors of N that are in the ready state (whose STATUS = 1) and set their STATUS = 2 (waiting state)
  • Step 6: EXIT

Example Of DFS Algorithm

Certainly, here is an example of the Depth-First Search (DFS) algorithm in action. Suppose we have the following graph:

      / \
     0   3


We can represent this graph using an adjacency list:

					import java.util.*;

class Graph {
    private int V;
    private LinkedList<Integer> adj[];

    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) {

    void DFSUtil(int v, boolean visited[]) {
        visited[v] = true;
        System.out.print(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 g = new Graph(4);

        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(0, 1);
        g.addEdge(3, 3);

        ("Following is Depth First Traversal " +
        "(starting from vertex 2)");