Depth First Search (DFS) Algorithm

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:

1. Breadth First Search (BFS)

2. 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

1. Starting Point: DFS starts at a selected starting vertex or node. The first selected node "marked" as visited.
2. Exploration: Starting with the currently visited node, DFS explores an unexplored (unvisited) adjacent to node. It repeats this procedure until it finds a node with no unvisited neighbors.
3. Backtracking: When a dead end is encountered, DFS returns to the nearest unexplored node and continues the procedure.
4. Completing the Search: DFS continues until all nodes are visited or a predefined target is met.

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);
  }
}

Following is Depth First Traversal (DFS):

0 1 3 2 4

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.

Space Complexity of DFS Algorithm

The space complexity of DFS algorithm is defined as O(V).

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.