Breadth-First Search (BFS)

It’s quite easy to find a node in a binary search tree, but, what if we are dealing with unordered tree or graph? In this case the problem become little bit tricky. Because, graph or tree might be very deep and breadth, directed or undirected or even worse it can be cycled. In such cases we have different searching algorithms that can be applied on graph, one of these algorithms is called Breadth-First Search (BFS).

The algorithm traverses a tree or graph starting from some node, it can be any node in the graph. On the diagram below node “A” will be the starting node.

bfs_2

Farther, the graph can be divided on levels. First level contains starting node, other levels contains child nodes of previous level. The levels in BFS can be illustrated in following way:

bfs_2_lvl

Graph is divided on levels, so – now it is time to successively traverse all nodes from the first level to the last level.

Sequence of the visited nodes will be following: A, B, C, D, E, F, G, H, I, J, K, L.

Voila! This is the breadth-first search.

Application

This is the one of the core graph algorithms and it has many applications. Here are some of them:

  1. First of all this algorithm can be used to find shortest path between two vertices. This is very useful in GPS navigation systems.
  2. Social networks like Facebook can use BFS to find all friends between two different persons. In fact, there is an average shortest path distance of 4.74 between users. It means that any two people separated on average by any five other people.
  3. Garbage collection uses it in copying garbage collection.
  4. Computer networks: peer to peer applications  like BitTorrent uses it to locate a file that was requested for download.
  5. Crawlers in Search Engines uses BFS to build index. BFS knows what vertices were visited and also search can be restricted by levels.
  6. Many other algorithms like Prim’s Minimum Spanning Tree and Dijkstra’s Single Source Shortest Path based or used BFS.
Implementation

Algorithm uses queue, and may use array for visited nodes. Information about visited nodes helps to void problems with cycled graphs.

Pre conditions:

  1. We need a graph.
  2. Initial node or vertex.

Algorithm:

  1. Enqueue initial node.
  2. Mark initial node as visited.
  3. If queue is not empty go to step 3.1, otherwise to step #4.
    1. Dequeue node from the queue. Farther the node will be called V.
    2. If V contains unvisited neighbours (the nodes that V is connected to), do steps from 3.2.1 to 3.2.n for these unvisited neighbours, otherwise goto step #3.
      1. Enqueue neighbour.
      2. Mark neighbour as visited.
    3. Go to step #3.
  4. End.

The complexity of the algorithm is O(|V|+|E|).

My version of BFS you can find on GITHUB: https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/algorithms/graph/BreadthFirstSearch.java.

2 thoughts on “Breadth-First Search (BFS)

Leave a Reply