Breadth First Search

BFS is an algorithm used to visit all the nodes in a graph or tree, visiting them by levels of distance from the origin node.

The example

If you have a tree with this structure:

                1

   2            3              4

 5   6        7   8          9   10

You would visit the nodes in this order (by levels):

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

The algorithm

You will visit each level 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).

The pseudocode

This algorithm can be expressed iteratively in a very easy way.

It uses a queue to make sure a new level is not visited until the current level is visited completely.

BFS(root):
    root.visited = True
    Queue q = [root]
    while not q.empty():
       x = q.dequeue()
       for neighbor in x.neighbors():
          if not neighbor.visited:
              neighbor.visited = True
              neighbor.parent = x
          q.enqueue(neighbor)

The complexity

|V| is the number of vertices (nodes) and |E| is the number of edges (connections).

Time: it will take the algorithm O(|V| + |E|) to visit all the nodes.

Space: it will use a space equivalent to O(|V|) due to the usage of a queue. It will also use O(|V|+|E|) if you use an adjacency list for the edges, or O(|V|2) if you use an adjacency matrix (when you know that you will have a maximum or fixed number of nodes).

Sources:

http://en.wikipedia.org/wiki/Breadth_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: