Graphs are useful in a lot of practical scenarios like in fields of networking, game theory and social media among many others. Often situations involving graphs involves traversal of the graph. In this post we are going to talk about one such graph traversal technique, Breadth First Search.

Breadth First Search or BFS

Breath First Search or BFS is a traversal or searching algorithm for graph and graph-like data structures. In this variation of graph traversal, we first traverse the breadth of the graph first before exploring the depth of the graph.

The basic idea here is to start at the root (or a random node for graph) and explore as many neighbours as possible before moving down to a different level i.e. in BFS once we pick a level, we explore the level completely before moving lower to some other level.

For example,

Animated Example of Breadth First Search
Animated Example of Breadth First Search

In the above graph we picked node 1 as the root, however this choice is arbitrary for a graph.

Algorithm

Pseudo Code :

graph[V][V]
visited[V]={false}

bfs(root)
    queue bfs_queue
    bfs_queue.push(root)
    visited[root]=true
    while bfs_queue.empty==false
        node=bfs_queue.front
        bfs_queue.pop
        for child in graph[node]
            if visited[child]=true
                continue
            visited[child]=true
            bfs_queue.push(child)

Time Complexity : O(V+E)

Space Complexity : O(V)

where V is the number of vertices and E is the number of edges.

Application

  • The BFS of a weighted graph produces a Minimum Spanning Tree of the graph.
  • BFS can be used to detect cycles in the graph.
  • BFS can be used to find the shortest path between two vertices in a graph.
  • BFS can be used to find all neighbour nodes of a vertex in a graph. This is useful in Social Networking websites, Navigation Systems, Peer-to-Peer Networks among others.
  • BFS is also used by Search Engines for web crawling.
  • In networks, broadcasted packet uses BFS to reach all the nodes.
  • BFS can be used to check if a graph is bipartite.

Breadth First Traversal is only one form of graph traversal and there are other methods also to traverse the graph but I will discuss them in other posts.