The Annals of Having Compensated To Complete Surveys

The depth-first search (DFS) is a method for finding a spanning forest of a connected graphMathworldPlanetmath (specifically, a spanning treeMathworldPlanetmath in the case of an undirected connected graph), and is a useful for other . In particular, the DFS is useful for finding the connected componentsMathworldPlanetmathPlanetmathPlanetmath of a graph. This article currently describes only the DFS for an undirected graph.



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


  • 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 CompletePlanetmathPlanetmathPlanetmathPlanetmath Surveys
Canonical name TheAnnalsOfHavingCompensatedToCompleteSurveys
Date of creation 2013-11-27 10:59:44
Last modified on 2013-11-27 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