Last Updated:

Depth-first search (DFS)

The Depth-first search (DFS) is a recursive algorithm for traversing the vertices of a graph. If the method of searching in width was made symmetrically (the vertices of the graph were viewed by levels), then this method involves moving deeper as long as possible. The impossibility of further advancement means that the next step will be to switch to the last, having several variants of movement (one of which is fully investigated), previously visited node (vertex).

The absence of the latter indicates one of two possible situations: either all the vertices of the graph have already been viewed, or all those that are available from the vertex taken as the initial vertex have been viewed, but not all (incoherent and directed graphs allow for the latter option).

Let's consider how the algorithm will behave on a specific example. The following undirected connected graph has a total of 5 vertices. First, you need to select the initial vertex. Whichever vertex is chosen as such, the graph is in any case fully investigated, since, as already mentioned, it is a connected graph without a single directional edge.
Let the crawl start at node 1, then the order of the sequence of nodes viewed is 1 2 3 5 4. If you start the execution, for example, with node 3, the crawl order is different: 3 2 1 5 4.
dfs

The algorithm for searching in depth is based on recursion, that is, the crawl function, as it runs, calls itself, which makes the code as a whole quite compact.

Pseudocode of the algorithm:

 

The header of the DFS(st)
function Output (st)
visited[st] ← visited;
For r=1 to n execute
If (graph[st, r] ≠ 0) and (visited[r] not visited) then DFS(r)

 

Here, DFS (depth-firstsearch) is the name of the function. Its only parameter st is the start node, passed from the main part of the program as an argument. Each of the elements of the visited logical array is pre-set to false, which means that each of the vertices will initially be marked as not visited.

A two-dimensional graph array is a matrix of the adjacency of a graph. Most of the attention should be focused on the last line. If the element of the matrix of adjacency at some step is 1 (and not 0) and the vertex with the same number as the checked column of the matrix has not been visited, then the function is recursively repeated. Otherwise, the function returns to the previous stage of recursion.

The code of the program in C++:

The code of the program in Pascal:

For ease of understanding, the result produced by the two programs is taken from the undirected graph given earlier as an example, and represented by the adjacency matrix graph[5][5].