Mastering Algorithms for Problem Solving in Java/

...

/

Introduction to Depth-First Search

Introduction to Depth-First Search

Learn about the history and evolution of depth-first search.

We'll cover the following...

In this lesson, we focus on a particular instantiation of the algorithm called depth-first search and primarily on the behavior of this algorithm in directed graphs. Although depth-first search can be accurately described as “whatever-first search with a stack,” the algorithm is normally implemented recursively rather than using an explicit stack:

Algorithm

DFS(v):‾if v is unmarkedmark vfor each edge v→wDFS(w)\underline{DFS(v):} \\ \hspace{0.4cm} if\space v\space is\space unmarked \\ \hspace{1cm} mark\space v \\ \hspace{1cm} for\space each\space edge\space v\rightarrow w \\ \hspace{1.7cm} DFS(w)

Press + to interact
import java.util.ArrayList;
import java.util.List;
public class Main {
    static void DFS(int v, boolean[] marked, List<List<Integer>> adj) {
        marked[v] = true;
        System.out.print(v + " ");
        for (int i = 0; i < adj.get(v).size(); i++) {
            int w = adj.get(v).get(i);
            if (!marked[w])
                DFS(w, marked, adj);
        }
    }
    public static void main(String[] args) {
        // Define the graph as an adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < 6; i++) {
            adj.add(new ArrayList<>());
        }
        adj.get(1).add(2);
        adj.get(1).add(3);
        adj.get(2).add(4);
        adj.get(3).add(4);
        adj.get(4).add(5);
        // Define the marked array
        boolean[] marked = new boolean[6];
        // Call DFS starting from vertex 1
        DFS(1, marked, adj);
    }
}

Explanation

  • Lines 3–12: These lines define a recursive method DFS that performs a depth-first search traversal of a graph represented as an adjacency list.
  • Lines 14–32: These lines define a graph as an adjacency list and call the DFS function to traverse the graph starting from vertex 1.

Optimization

We can make this algorithm slightly faster (in practice) by checking whether a node is marked before we recursively explore it. This modification ensures that we call DFS(v)DFS(v) only once for each vertex vv. We can further modify the algorithm to compute other useful information about the vertices and edges by introducing two black box subroutines, PreVisitPreVisit and PostVisitPostVisit, which we leave unspecified for now.

Algorithm

DFS(v ...