Prab: CSV import

2024-06-05T22:37:32Z

CSV import

New page

[[File:Depth-first-tree.svg|thumb|Depth-first-tree]] [[file:Depth-First-Search.gif|right|thumb|Depth-First-Search]] [[file:graph.traversal.example.svg|right|thumb|graph.traversal.example]] [[file:Tree_edges.svg|thumb|Tree_edges]] [[file:If-then-else-control-flow-graph.svg|thumb|If-then-else-control-flow-graph]] [[file:Graph.traversal.example.svg|thumb|Graph.traversal.example]] [[file:MAZE_30x20_DFS.ogv|thumb|MAZE_30x20_DFS.ogv]] '''Depth-first search''' ('''DFS''') is an algorithm for traversing or searching [[tree (data structure)|tree]] or [[graph (discrete mathematics)|graph]] data structures. The algorithm starts at the [[root (graph theory)|root]] node (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

==Algorithm==
The basic idea of DFS is to start from the root (or any arbitrary node) and mark the node and move to an adjacent unmarked node and continue this process until there is no unmarked adjacent node. Then backtrack and check for other unmarked nodes and traverse them. Finally, print the nodes in the path.

===Pseudocode===
The pseudocode for DFS is as follows:

'''Recursive DFS:'''
<syntaxhighlight lang="pseudocode">
procedure DFS(G, v) is
label v as discovered
for all directed edges from v to w that are in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G, w)
</syntaxhighlight>

'''Iterative DFS:'''
<syntaxhighlight lang="pseudocode">
procedure DFS-iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
</syntaxhighlight>

==Applications==
DFS is used in various applications, including:
* [[Topological sorting]]
* [[Finding connected components]]
* [[Pathfinding]]
* [[Solving puzzles]] with only one solution, such as mazes

==Properties==
* DFS can be implemented using [[recursion]] or using a [[stack (abstract data type)|stack]].
* The time complexity of DFS is O(V + E), where V is the number of vertices and E is the number of edges.
* The space complexity of DFS is O(V) in the worst case.

==Related Algorithms==
* [[Breadth-first search]]
* [[Dijkstra's algorithm]]
* [[A* search algorithm]]

==See Also==
* [[Graph theory]]
* [[Tree traversal]]
* [[Algorithm]]

==Related Pages==
* [[Graph (discrete mathematics)]]
* [[Tree (data structure)]]
* [[Breadth-first search]]
* [[Topological sorting]]
* [[Pathfinding]]

[[Category:Graph algorithms]]
[[Category:Search algorithms]]
[[Category:Computer science]]

{{Graph algorithms}}
{{Algorithm-stub}}

Depth-first search - Revision history

Prab: CSV import