Depth search (depth-first search)

One of the methods of systematically traversing the vertices of a graph is called depth-first search . The depth-first search strategy, as its name implies, is to go "in depth" of the graph as far as possible. When performing a depth search, all edges that go out of a vertex opened by the last one are examined and leave the top only when no unexplored edges remain - this returns to the top from which the top v was opened. This process continues until all the vertices reachable from the original are opened. If at the same time there are undiscovered vertices, then one of them is selected as the new original vertex and the search is repeated from it. This process is repeated until all vertices are open.

When vertex v is opened in the process of scanning the adjacency list of an already open vertex, the search procedure records this event by setting the predecessor's field v prev [v] to u. Unlike the search in width, where the preceding subgraph forms a tree, when searching in depth, the preceding subgraph can consist of several trees , since the search can be performed from several original vertices.

As in the process of performing the search in width, the vertices of the graph are colored in different colors indicating their condition. Each vertex is initially white, then when it opens (discover), it turns gray in the search process, and when it finishes (finish), when its adjacency list is completely scanned, it turns black. This technique ensures that each vertex is ultimately located in only one depth-first search tree.

In addition to building a search depth forest, depth search also places timestamps on vertices. Each vertex has two such labels — the first d [v] , which indicates when the vertex y opens (and turns gray), and the second — f [v] , which captures the moment when the search completes scanning the adjacency list of j and she turns black. These tags are used by many algorithms and are useful when considering the depth of search behavior.

Formal description [up]

  DFS (G)
 1 for (For) each vertex u є V [G) 
 2 do color [u] "- WHITE 
 3 prev [u] "- NIL 
 4 time "- About 
 5 for (For) each vertex u E V [G] 
 6 do if color [u] = white
 7 then DFS_Visit (u) 

 DFS_Visit (u)
 1 color [u] "- GRAY // White top open u
 2 time "- time + 1
 3 d [u] «- time
 4 for (For) each vertex v є Adj [u] // Investigation of the edge (u, v). 
 5 do if color [v] = white 
 6 then prev [v] "- u 
 1 DFS_Visit (v) 
 8 color [u] "- BLACK // End 
 9 f [u] "- time " - time +1 

In lines 1-3, all vertices are painted white, and their fields nx are initialized to nil. Line 4 resets the global time counter. In lines 5-7, all vertices from V are checked alternately, and when a white vertex is detected, it is processed using the DFS_Visit procedure. Each time you call the DFS_Visit (u) procedure on line 7, the vertex becomes the root of the new tree in the search for depth forest. When returning from the DFS procedure, each vertex is matched with two points in time — the discovery time d [u] and the finishing time (f time) f [u].

Each time DFS_Visit (ix) is called, the vertex is initially white. In line 1 it is colored gray, in line 2 the global variable time increases, and in line 3 the new value of the variable time is recorded in the open time field d [u] . In lines 4-7, all vertices adjacent to u are examined, and recursive visits to white vertices are performed. When considering row 4 vertices v є Adj [and], we say that the edge ( u, v ) is explored by depth-first search. Finally, after all edges leaving u are examined, lines 8–9 are vertex and colored black, and the time for completing work with it is recorded in the f [u] field.

Evaluation of complexity [up]

Cycles in lines 1-3 and 5-7 of the DFS procedure are performed in the o (V) time, excluding the time required to call the DFS_Visit procedure. The DFS_VISIT procedure is called exactly once for each vertex v є V, since it is called only for white vertices, and the first thing it does is to color the vertex passed as a parameter to gray. During the execution of DFS_Visit (v), the loop in lines 4-7 is executed | Adj [v] | time. Insofar as

The total cost of executing lines 4-7 of the DFS_Visit procedure is o (E).

The running time of the DFS procedure is thus o (V + E) .

Example [up]

Depth traversal order:

The graph and spanning tree obtained by traversing its vertices using the depth search method: