# The Annals of Having Compensated To Complete Surveys

The depth-first 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.

\theoremstyle

definition

###### Definition (DFS on an Undirected Graph)

Assume that the undirected graph $G=(V,E)$ is connected. The DFS proceeds as follows.

1. 1.

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

2. 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 TheAnnalsOfHavingCompensatedToCompleteSurveys 2013-11-27 10:59:44 2013-11-27 10:59:44 jacou (1000048) (0) 18 jacou (0) Algorithm msc 05C85 DFS GraphTheory SpanningTree ConnectedComponents