The Annals of Having Compensated To Complete Surveys
The depthfirst search (DFS) is a method for finding a spanning forest of a connected graph^{} (specifically, a spanning tree^{} in the case of an undirected connected graph), and is a useful for other . In particular, the DFS is useful for finding the connected components^{} of a graph. This article currently describes only the DFS for an undirected graph.
definition
Definition (DFS on an Undirected Graph)
Assume that the undirected graph $G\mathrm{=}\mathrm{(}V\mathrm{,}E\mathrm{)}$ is connected. The DFS proceeds as follows.

1.
Fix a vertex $v$ in $G$ and mark it as visited.

2.
For each edge $(v,w)$ from $v$ to $w$:

–
If $w$ has been visited, do nothing.

–
If $w$ has not been visited, perform a DFS starting from $w$.

–
When the search is , it $G$ into two sets. One the directed edges between visited vertices, called tree edges, which form a directed spanning tree of the graph. The other the remaining edges of $G$ which were left unexamined because they were incident^{} on a vertex that was already visited at some in the search. Because these unexamined edges can be seen as returning to vertices that were previously visited, they are called back edges.
References
 1 Swamy, M.N.S., Thulasiraman, K., Graphs, Networks and Algorithms, John Wiley and Sons, New York, 1981.
Title  The Annals of Having Compensated To Complete^{} Surveys 

Canonical name  TheAnnalsOfHavingCompensatedToCompleteSurveys 
Date of creation  20131127 10:59:44 
Last modified on  20131127 10:59:44 
Owner  jacou (1000048) 
Last modified by  (0) 
Numerical id  18 
Author  jacou (0) 
Entry type  Algorithm 
Classification  msc 05C85 
Synonym  DFS 
Related topic  GraphTheory 
Related topic  SpanningTree 
Related topic  ConnectedComponents 