Depth First Search

DFS is an algorithm used to visit all the nodes in a graph or tree, by visiting them branch by branch to their maximum depth.

 

The example

If you have a tree with this structure:

                1

   2            3              4

 5   6        7   8          9   10

You would visit the node in this order (by branches):

1-2-5-6-3-7-8-4-9-10

The algorithm

You will visit each branch of nodes, starting with the selected origin node. Each node that you visit will be marked as such and will know who was its parent (the node of the previous level from which we came). When a branch has no more nodes, the algorithm backtracks to the last level with unexplored branches.

The pseudocode

This algorithm can be expressed iteratively or recursively.

It uses a stack to make sure to visit the most recently explored nodes before continuing with the current level. This ensures to visit children first (branch) and then siblings. Recursion allows this behavior too, since each discovered neighbor is recursively explored until no more children are found.

Iterative:

DFS(root):
    root.visited = True
    Stack s = [root]
    while not s.empty():
        x = s.pop()
        for neighbor in x.neighbors():
            if not neighbor.visited:
                neighbor.visited = True
                neighbor.parent = x
            s.push(neighbor)

Recursive:

DFS(root):
    root.visited = True
    for neighbor in root.neighbors():
        if not neighbor.visited:
            neighbor.parent = root
            DFS(neighbor)

The complexity

|V| is the number of vertices (nodes), |E| is the number of edges (connections), b is the branching factor and d is the depth.

Time: it will take the algorithm O(|E|) to visit all the nodes when there is no repetition (as in a tree), and O(bd) when there is repetition (as in a graph with multiple connections or with cycles).

Space: it will use a space equivalent to O(|V|) in a graph without repetition or O(longest path length searched) for implicit graphs without elimination of duplicate nodes.

 

Sources:

http://en.wikipedia.org/wiki/Depth_first_search

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: