# 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).

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++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 | #include "stdafx.h" #include <iostream> using namespace std; const int n=5; int i, j; bool *visited=new bool[n]; //graph adjacency matrix int graph[n][n] = { {0, 1, 0, 0, 1}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 1}, {1, 0, 1, 1, 0} }; // depth-first search void DFS(int st) { int r; cout<<st+1<<" "; visited[st]=true; for (r=0; r<=n; r++) if ((graph[st][r]!=0) && (!visited[r])) DFS(r); } // main function void main() { setlocale(LC_ALL, "Rus"); int start; cout<<"Graph Adjacency Matrix: "<<endl; for (i=0; i<n; i++) { visited[i]=false; for (j=0; j<n; j++) cout<<" "<<graph[i][j]; cout<<endl; } cout<<"Starting vertex >>"; cin>>start; //array of visited vertices bool *vis=new bool[n]; cout<<"Travel order: "; DFS(start-1); delete []visited; system("pause>>void"); } |

### The code of the program in Pascal:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | program DepthFirstSearch; usescrt; const n=5; var i, j, start: integer; visited: array[1..n] of boolean; const graph: array[1..n,1..n] of byte = ((0, 1, 0, 0, 1), (1, 0, 1, 1, 0), (0, 1, 0, 0, 1), (0, 1, 0, 0, 1), (1, 0, 1, 1, 0)); {depth-first search} procedure DFS(st: integer); varr: integer; begin write(st:2); visited[st]:=true; for r:=1 to n do if (graph[st, r]<>0) and (not visited[r]) then DFS(r); end; {main program block} begin clrscr; writeln('Adjacency Matrix:'); for i:=1 to n do begin visited[i]:=false; for j:=1 to n do write(graph[i, j],' '); writeln; end; write('Starting node >> '); read(start); writeln('Travel result'); DFS(start); end. |

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