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