Monday, 11 September 2017

Algorithms | Breadth-first search (BFS) and Its application

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

Pseudo code
Input: A graph Graph and a starting vertex root of Graph
Output: Goal state. The parent links trace the shortest path back to root

A non-recursive implementation of breadth-first search:
Breadth-First-Search(Graph, root):
      create empty set S
      create empty queue Q     

      add root to S
      Q.enqueue(root)                     

      while Q is not empty:
          current = Q.dequeue()
          if current is the goal:
            return current
                  for each node n that is adjacent to current:
                  if n is not in S:
                        add n to S
                        Q.enqueue(n)

Applications of Breadth First Traversal
1) Ford–Fulkerson algorithm
Ford–Fulkerson method is used to computing the maximum flow in a flow network. We can either use Breadth First or Depth First Traversal to find the maximum flow. Breadth First Traversal is preferred as it reduces worst case time complexity to O(VE2).

2) Construction of the failure functions of the Aho-Corasick pattern matcher.

3) Shortest Path and Minimum Spanning Tree for unweighted graph
In the unweighted graph, the shortest path is the path with least number of edges. With Breadth First, we always reach a vertex from given source using a minimum number of edges. Also, in case of unweighted graphs, any spanning tree is Minimum Spanning Tree and we can use either Depth or Breadth first traversal for finding a spanning tree.

4) Peer to Peer Networks
 In Peer to Peer Networks like BitTorrent, Breadth First Search is used to find all neighbor nodes.

5) Crawlers in Search Engines
Crawlers build the index using Breadth First. The idea is to start from source page and follow all links from source and keep doing same. Depth First Traversal can also be used for crawlers, but the advantage with Breadth First Traversal is depth or levels of the built tree can be limited.

6) Social Networking Websites
In social networks, we can find people within a given distance ‘k’ from a person using Breadth First Search till ‘k’ levels.

7) GPS Navigation systems
Breadth First Search is used to find all neighboring locations.

8) Broadcasting in Network
In networks, a broadcasted packet follows Breadth First Search to reach all nodes.

9) In garbage collection
Copying garbage collection, Cheney's algorithm
Breadth First Search is used in copying garbage collection using Cheney’s algorithm. Refer this and for details. Breadth First Search is preferred over Depth First Search because of better locality of reference:

10) Cycle detection in undirected graph
In undirected graphs, either Breadth First Search or Depth First Search can be used to detect cycle. In the directed graph, only depth first search can be used.

11) To test if a graph is Bipartite
We can either use Breadth First or Depth First Traversal.

12) Path Finding
We can either use Breadth First or Depth First Traversal to find if there is a path between two vertices.

13) Finding all nodes within one connected component
We can either use Breadth First or Depth First Traversal to find all nodes reachable from a given node.

14) Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be reconstructed in an efficient manner.

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...