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
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 listList<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 arrayboolean[] marked = new boolean[6];// Call DFS starting from vertex 1DFS(1, marked, adj);}}
Explanation
- Lines 3–12: These lines define a recursive method
DFSthat 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
DFSfunction 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 only once for each vertex . We can further modify the algorithm to compute other useful information about the vertices and edges by introducing two black box subroutines, and , which we leave unspecified for now.
Algorithm
...