Depth-first search
In computer science, depth-first search (DFS) is a method used for traversing a graph. It starts at an arbitrary item of a graph and explores as far as possible along each branch before backtracking.
Implementation
Recursive
<syntaxhighlight lang="java"> void depthFirstSearch(Item root) {
if (root == null) return;
root.found = true;
for (Item neighbor : root.neighbors()) {
if (!neighbor.found) depthFirstSearch(n);
}
} </syntaxhighlight>
Uses
An example: To make a program that searches all the files on your computer, it has to be able to keep track of which folders it has already searched through, so it doesn't look through the same folder twice. So it does this: inside each folder, it goes as far down into subfolders as it can. Every time it checks something to see if it matches, it will write it down on the list as "already searched". Then it will leave and go to the next subfolder. If there are no subfolders left, it will backtrack another step and look in the next bigger folder. It does this until it has looked through everything.
We know that this is the best way to make sure the search program looks through every folder and file once, and only once, because graph theory has proved it.
Depth-first Search Media
Order in which the nodes get expanded
A simple graph to illustrate depth-first traversal. Created with Graphviz neato and tweaked with Inkscape.
The four types of edges defined by a spanning tree
Simple if-then-else control flow graph.
-
The example graph, copied from above
Randomized algorithm similar to depth-first search used in generating a maze.
