Depth-first search

From Simple English Wikipedia, the free encyclopedia
Jump to navigation Jump to 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.

Animated example of a depth-first search within a tree.

Implementation[change | change source]

Recursive[change | change source]

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

Related pages[change | change source]