Depth-First Search (DFS)

The depth-first search of a graph starts from a vertex in the graph and visits all vertices in the graph as far as possible before backtracking.
The depth-first search of a graph is like the depth-first search of a tree discussed in Tree Traversal, Tree Traversal. In the case of a tree, the search starts from the root. In a graph, the search can start from any vertex.

A depth-first search of a tree first visits the root, then recursively visits the subtrees of the root. Similarly, the depth-first search of a graph first visits a vertex, then it recursively visits all the vertices adjacent to that vertex. The difference is that the graph may contain cycles, which could lead to an infinite recursion. To avoid this problem, you need to track the vertices that have already been visited.

The search is called depth-first because it searches “deeper” in the graph as much as possible. The search starts from some vertex v. After visiting v, it visits an unvisited neighbor of v. If v has no unvisited neighbor, the search backtracks to the vertex from which it reached v. We assume that the graph is connected and the search starting from any vertex can reach all the vertices.

Depth-First Search Algorithm

The algorithm for the depth-first search is described in the code below.

Input: G = (V, E) and a starting vertex v
Output: a DFS tree rooted at v
1 Tree dfs(vertex v) {
2 visit v;
3 for each neighbor w of v
4 if (w has not been visited) {
5 set v as the parent for w in the tree;
6 dfs(w);
7 }
8 }

You can use an array named isVisited to denote whether a vertex has been visited. Initially, isVisited[i] is false for each vertex i. Once a vertex, say v, is visited, isVisited[v] is set to true.

Consider the graph in Figure below (a). Suppose we start the depth-first search from vertex 0. First visit 0, then any of its neighbors, say 1. Now 1 is visited, as shown in Figure below (b). Vertex 1 has three neighbors—0, 2, and 4. Since 0 has already been visited, you will visit either 2 or 4. Let us pick 2. Now 2 is visited, as shown in Figure below (c). Vertex 2 has three neighbors: 0, 1, and 3. Since 0 and 1 have already been visited, pick 3. 3 is now visited, as shown in Figure below (d). At this point, the vertices have been visited in this order:

0, 1, 2, 3

Since all the neighbors of 3 have been visited, backtrack to 2. Since all the vertices of 2 have been visited, backtrack to 1. 4 is adjacent to 1, but 4 has not been visited. Therefore, visit 4, as shown in Figure below (e). Since all the neighbors of 4 have been visited, backtrack to 1.
Since all the neighbors of 1 have been visited, backtrack to 0. Since all the neighbors of 0 have been visited, the search ends.

Since each edge and each vertex is visited only once, the time complexity of the dfs method is O(|E| + |V|), where |E| denotes the number of edges and |V| the number of vertices.

Implementation of Depth-First Search

The algorithm for DFS in the code above uses recursion. It is natural to use recursion to implement it. Alternatively, you can use a stack.

The dfs(int v) method is implemented in lines 164–193 in AbstractGraph.java. It returns an instance of the Tree class with vertex v as the root. The method stores the vertices searched in the list searchOrder (line 165), the parent of each vertex in the array parent (line 166), and uses the isVisited array to indicate whether a vertex has been visited (line 171). It invokes the helper method dfs(v, parent, searchOrder, isVisited) to perform a depth-first search (line 174).

In the recursive helper method, the search starts from vertex u. u is added to searchOrder in line 184 and is marked as visited (line 185). For each unvisited neighbor of u, the method is recursively invoked to perform a depth-first search. When a vertex e.v is visited, the parent of e.v is stored in parent[e.v] (line 189). The method returns when all vertices are visited for a connected graph, or in a connected component.

The code below gives a test program that displays a DFS for the graph in Figure above starting from Chicago. The graphical illustration of the DFS starting from Chicago is shown in Figure below.

public class TestDFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<String> graph = new UnweightedGraph<>(vertices, edges);
        AbstractGraph<String>.Tree dfs = graph.dfs(graph.getIndex("Chicago"));

        java.util.List<Integer> searchOrders = dfs.getSearchOrder();
        System.out.println(dfs.getNumberOfVerticesFound() + " vertices are searched in this DFS order:");
        for(int i = 0; i < searchOrders.size(); i++)
            System.out.print(graph.getVertex(searchOrders.get(i)) + " ");
        System.out.println();

        for(int i = 0; i < searchOrders.size(); i++)
            if(dfs.getParent(i) != -1)
                System.out.println("parent of " + graph.getVertex(i) + " is " + graph.getVertex(dfs.getParent(i)));
    }

}

12 vertices are searched in this DFS order:
Chicago Seattle San Francisco Los Angeles Denver
Kansas City New York Boston Atlanta Miami Houston Dallas
parent of Seattle is Chicago
parent of San Francisco is Seattle
parent of Los Angeles is San Francisco
parent of Denver is Los Angeles
parent of Kansas City is Denver
parent of Boston is New York
parent of New York is Kansas City
parent of Atlanta is New York
parent of Miami is Atlanta
parent of Dallas is Houston
parent of Houston is Miami

Applications of the DFS

The depth-first search can be used to solve many problems, such as the following:

• Detecting whether a graph is connected. Search the graph starting from any vertex. If the number of vertices searched is the same as the number of vertices in the graph, the graph is connected. Otherwise, the graph is not connected.
• Detecting whether there is a path between two vertices.
• Finding a path between two vertices.
• Finding all connected components. A connected component is a maximal connected subgraph in which every pair of vertices are connected by a path.
• Detecting whether there is a cycle in the graph.
• Finding a cycle in the graph.
• Finding a Hamiltonian path/cycle. A Hamiltonian path in a graph is a path that visits each vertex in the graph exactly once. A Hamiltonian cycle visits each vertex in the graph exactly once and returns to the starting vertex.

The first six problems can be easily solved using the dfs method in AbstractGraph.java. To find a Hamiltonian path/cycle, you have to explore all possible DFSs to find the one that leads to the longest path. The Hamiltonian path/cycle has many applications, including for solving the well-known Knight’s Tour problem.

The above is the detailed content of Depth-First Search (DFS). For more information, please follow other related articles on the PHP Chinese website!