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

void depthFirstSearch(Item root) {
    if (root == null) return;
    root.found = true;
    for (Item neighbor : root.neighbors()) {
        if (!neighbor.found) depthFirstSearch(n);
    }
}

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.

Related pages