Depth First Search (DFS) Algorithm

Last Updated: 06 October, 2024 🕓 5 Mins

Graph traversal is a technique for searching a vertex (node) in a graph. It can also be used to determine the order in which vertices are visited during the search process. Graph traversal determines which edges to use during the search process so as to avoid loops.

There are the following two possible way of graph traversal:

Breadth First Search (BFS)

Depth First Search (DFS)

In the graph tutorial, we are going learn all about Depth First Search (DFS).

What is the Depth First Search (DFS) Algorithm?

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a root node and explores its neighbors one by one, going deeper into the graph until it hits a dead end or a previously visited node. Then, it backtracks to the last node with unexplored neighbors and continues the process.

How the DFS algoritham works

Example of DFS (Depth First Search)

  
  import java.util.Iterator;
  import java.util.LinkedList;
  
  public class DFSExample {
    private LinkedList<Integer> adjLists[];
    private boolean visited[];
    
    DFSExample(int number_of_vertices) {
      adjLists = new LinkedList[number_of_vertices];
      visited = new boolean[number_of_vertices];
      
      for (int i = 0; i < number_of_vertices; i++)
        adjLists[i] = new LinkedList<Integer>();
    }
    
    // Add edges
    void addEdge(int src, int dest) {
      adjLists[src].add(dest);
    }
    
    // DFS algorithm
    void DFS(int vertex) {
      visited[vertex] = true;
      System.out.print(vertex + " ");
      
      Iterator<Integer> ite = adjLists[vertex].listIterator();
      while (ite.hasNext()) {
        int adj = ite.next();
        if (!visited[adj])
          DFS(adj);
      }
    }
    
    public static void main(String args[]) {
      DFSExample gfs = new DFSExample(5);
      
      gfs.addEdge(0, 1);
      gfs.addEdge(0, 2);
      gfs.addEdge(1, 3);
      gfs.addEdge(2, 4);
      
      System.out.println("Following is Depth First Traversal (DFS):");
      
      // Start DFS from vertex 0
      gfs.DFS(0);
    }
  }

Time Complexity of DFS Algorithm

In the DFS algorithm, the time complexity defined as O(V + E), where V represents the number of vertices and E represents the number of edges in the graph.

Applications of the DFS Algorithm

Pathfinding Algorithms: DFS can be applied to pathfinding algorithms, such as finding the shortest path (from the start to the end) in a maze or detecting network connectivity.

Detect Cycles in Graphs: DFS is used to detect cycles in graphs (for directed and undirected graphs) by tracking back edges.

Topological Sorting: In directed acyclic graphs (DAGs), DFS is used to perform topological sorting, which is important in dependency management and scheduling.

To find connected components: DFS can find all connected components in an undirected graph by exploring each vertex and its neighbors.

Solving Puzzles: DFS is used to solve puzzles that require exploring each possible configuration, such as Sudoku and the N-Queens problem.

Network Analysis: The structure of networks, including social and computer networks, can be investigated and analyzed using DFS.