What are some applications of Breadth First Search?

Software Development
#1

Breadth-first search (BFS) algorithm is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores along adjacent nodes and proceeds recursively.

Pseudocode:

BFS(v):
                for each vertex i
                        do d[i] = inf
                d[v] = 0
                queue q
                q.push(v)
                while q is not empty
                        u = q.front()
                        q.pop()
                        for each w in adj[u]
                                if d[w] == inf
                                        then d[w] = d[u] + 1, q.push(w)

Applications:

  • Shortest Path and Minimum Spanning Tree for unweighted graph
  • Find neighboring nodes like in Peer to Peer Networks, Crawlers in search engine, potential friends in social networks, GPS navigation system, broadcasting in network and many others.
  • In Garbage Collection: Breadth First Search is used in copying garbage collection using Cheney’s algorithm.
  • Cycle detection in undirected graph
  • Ford–Fulkerson algorithm
  • To test if a graph is Bipartite
  • Path Finding