Editing Depth-first search (section)

==Applications==
[[File:MAZE 30x20 DFS.ogv|thumb|upright=1.5|Randomized algorithm similar to depth-first search used in generating a maze.]]
Algorithms that use depth-first search as a building block include:
* Finding [[Connected component (graph theory)|connected components]].
* [[Topological sorting]].
* Finding 2-(edge or vertex)-connected components.
* Finding 3-(edge or vertex)-connected components.
* Finding the [[Bridge (graph theory)#Bridge-finding algorithm|bridges]] of a graph.
* Generating words in order to plot the [[limit set]] of a [[Group (mathematics)|group]].
* Finding [[strongly connected components]].
* Determining whether a species is closer to one species or another in a phylogenetic tree.
* [[Planarity testing]].<ref>{{citation
 | last1 = Hopcroft | first1 = John | author1-link = John Hopcroft
 | last2 = Tarjan | first2 = Robert E. | author2-link = Robert Tarjan
 | doi = 10.1145/321850.321852
 | issue = 4
 | journal = [[Journal of the ACM|Journal of the Association for Computing Machinery]]
 | pages = 549–568
 | title = Efficient planarity testing
 | volume = 21
 | year = 1974| url = https://ecommons.cornell.edu/bitstream/1813/6011/1/73-165.pdf
 | hdl = 1813/6011
 | s2cid = 6279825 | hdl-access = free
 }}.</ref><ref>{{citation
 | last1 = de Fraysseix | first1 = H.
 | last2 = Ossona de Mendez | first2 = P. | author2-link = Patrice Ossona de Mendez
 | last3 = Rosenstiehl | first3 = P. | author3-link = Pierre Rosenstiehl
 | journal = International Journal of Foundations of Computer Science
 | pages = 1017–1030
 | title = Trémaux Trees and Planarity
 | volume = 17
 | year = 2006
 | doi = 10.1142/S0129054106004248
 | issue = 5| arxiv=math/0610935| bibcode = 2006math.....10935D
 | s2cid = 40107560
 }}.</ref>
* Solving puzzles with only one solution, such as [[maze]]s. (DFS can be adapted to find all solutions to a maze by only including nodes on the current path in the visited set.)
* [[Maze generation]] may use a randomized DFS.
* Finding [[Biconnected graph|biconnectivity in graphs]].
* [[Primogeniture#Absolute_primogeniture|Succession]] to the throne shared by the [[Commonwealth realms]].<ref>{{citation|last1=Baccelli|first1=Francois|last2=Haji-Mirsadeghi|first2=Mir-Omid|last3=Khezeli|first3=Ali|editor-last=Sobieczky|editor-first=Florian|contribution=Eternal family trees and dynamics on unimodular random graphs|doi=10.1090/conm/719/14471|location=Providence, Rhode Island|mr=3880014|pages=85–127|publisher=American Mathematical Society|series=Contemporary Mathematics|title=Unimodularity in Randomly Generated Graphs: AMS Special Session, October 8–9, 2016, Denver, Colorado|volume=719|year=2018|arxiv=1608.05940 |isbn=978-1-4704-3914-9 |s2cid=119173820 }}; see [https://books.google.com/books?id=7dV7DwAAQBAJ&pg=PA93 Example 3.7, p. 93]</ref>