Lecture
Depth-first search (DFS) is a recursive algorithm for traversing the vertices of a graph. Whereas breadth-first search proceeds symmetrically (the vertices of the graph are examined level by level), this method involves moving as deep as possible for as long as possible. The impossibility of moving further means that the next step will be to move back to the most recently visited node that has several possible directions of movement (one of which has been fully explored). The absence of such a node indicates one of two possible situations: either all vertices of the graph have already been examined, or all vertices reachable from the vertex taken as the starting point have been examined, but not all vertices of the graph (disconnected and directed graphs allow for the latter case).
Let us consider how the algorithm behaves using a specific example. The undirected connected graph shown below has a total of 5 vertices.
First, a starting vertex must be chosen. Whichever vertex is chosen as such, the graph will in any case be fully explored, since, as already mentioned, this is a connected graph without a single directed edge.
Suppose the traversal begins at node 1; then the order of the sequence of visited nodes will be as follows: 1 2 3 5 4. If execution begins, for example, at node 3, the traversal order will be different: 3 2 1 5 4.
The depth-first search algorithm is based on recursion, i.e., the traversal function, as it executes, calls itself, which makes the code as a whole rather compact. Pseudocode of the algorithm:
Function header DFS(st)
Output (st)
visited[st] ← visited;
For r=1 to n do
If (graph[st, r] ≠ 0) and (visited[r] not visited) then DFS(r)
Here DFS (depth-first search) is the name of the function. Its only parameter, st, is the starting node, passed from the main part of the program as an argument. Each element of the boolean array visited is initially assigned the value false, i.e., each of the vertices is initially marked as not visited. The two-dimensional array graph is the adjacency matrix of the graph. Most of the attention should be focused on the last line. If an element of the adjacency matrix is, at some step, equal to 1 (and not 0), and the vertex with the same number as the column of the matrix being checked has not yet been visited, then the function is called recursively. Otherwise the function returns to the previous stage of recursion.
|
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 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< |
|
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;
uses crt; 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); var r: 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 vertex >> '); read(start); writeln('Traversal result'); DFS(start); end. |
For ease of understanding the result produced by the two programs, the undirected graph given earlier as an example, and represented by the adjacency matrix graph, is used.
Comments