Close
Close

Breadth First Search


Breadth-first search or BFS is a searching technique for graphs in which we first visit all the nodes at the same depth first and then proceed visiting nodes at a deeper depth. For example, in the graph given below, we would first visit the node 1, and then after visiting the nodes 2, 3 and 4, we can proceed to visit any deeper node i.e., nodes 5, 6, 7 and 8.

graph

Let's look at the animation given below to see the working of BFS.

A node can be reached from different nodes using different paths but we need to visit each node only once. So, we mark each node differently into 3 categories - unvisited, discovered and complete.

different path for same node

visit a node in bfs only if not discovered

Initially, all nodes are unvisited. After visiting a node for the first time, it becomes discovered.

A node is complete if all of its adjacent nodes have been visited.

Thus, all the adjacent nodes of a complete node are either discovered or complete.

The terms unvisited, discovered and complete are not standard ones. We are using them only to explain the concept in this context.

Generally, three different colors i.e., white, gray and black are used to represent unvisited, discovered and complete respectively.

visited, discovered and complete node in bfs

Thus after visiting a node, we first visit all its sibling and then their children. We can use a first in first out (FIFO) queue to achieve this. Starting from the source, we can put all its adjacent nodes in a queue.

using queue bfs

Now, we will visit the first element of the queue and put all its adjacent nodes in the queue.

step for bfs

We can see that the queue has all the nodes at the same distance first (say d) and then other nodes at the distance (d+1).

distance of nodes in bfs

In this way, we can visit the nodes at a smaller distance from the source first before proceeding for the nodes at larger distances and thus, can accomplish BFS.

full steps for bfs

animation of BFS

Code for BFS


We are going to use queue for the implementation of the BFS.

Our function is going to take the graph (G) and the source node (s) as its input - BFS(G, s).

Our next task is to make all of its nodes unvisited i.e., white. As discussed in the previous chapter, the adjacency-list representation of the graph has list of all its vertices (G.V), so we will iterate over it to make all its element white.

for i in G.V
  i.color = white

We are going to start from the source, so let's make the source node discovered i.e., gray - s.color = gray.

Now, we need to initialize the queue. After discovering a new node, we will enqueue all of its adjacent nodes into this queue. We will dequeue this queue to start visiting a new node.

So, we will start by putting the source node in the queue first.

queue.enqueue(s)

We will iterate until the queue becomes empty and dequeue the node to get a node to work with.

while !q.is_empty
  u = queue.dequeue()

Now, we need to enqueue all of the adjacent nodes of the node we got by dequeuing the queue.

We know that we store all the adjacent nodes of a node in an array 'Adj'. So, Adj[u] is the list of all the adjacent nodes of the node u.

while !q.is_empty
  u = queue.dequeue()
  for i in Adj[u]
    if i.color == white // only if the node is not yet discovered
      i.color = gray //mark it discovered
      queue.enqueue(i)
  u.color = black // all adjacent nodes of this node are discovered

BFS(G, s)
  for i in G.V
    i.color = white
  s.color = gray

  queue.enqueue(s)

  while !q.is_empty
    u = queue.dequeue()
    for i in Adj[u]
      if i.color == white // only if the node is not yet discovered
        i.color = gray // mark it discovered
        queue.enqueue(i)
    u.color = black // all adjacent nodes of this node are discovered
  • C
  • Python
  • Java
#include <stdio.h>
#include <stdlib.h>
enum color{White, Gray, Black};

/*
  Node for linked list of adjacent elements.
  This will contain a pointer for next node.
  It will not contain the real element but the index of
  element of the array containing all the vertices V.
*/
typedef struct list_node {
  int index_of_item;
  struct list_node *next;
}list_node;

/*
  Node to store the real element.
  Contain data and pointer to the
  first element (head) of the adjacency list.
*/
typedef struct node {
  int data;
  enum color colr;
  list_node *head;
}node;

/*
  Graph will contain number of vertices and
  an array containing all the nodes (V).
*/
typedef struct graph{
  int number_of_vertices;
  node heads[]; // array of nodes to store the list of first nodes of each adjacency list
}graph;

node* new_node(int data) {
  node *z;
  z = malloc(sizeof(node));
  z->data = data;
  z->head = NULL;
  z->colr = White;

  return z;
}

list_node* new_list_node(int item_index) {
  list_node *z;
  z = malloc(sizeof(list_node));
  z->index_of_item = item_index;
  z->next = NULL;

  return z;
}

// make a new graph
graph* new_graph(int number_of_vertices) {
  //number_of_vertices*sizeof(node) is the size of the array heads
  graph *g = malloc(sizeof(graph) + (number_of_vertices*sizeof(node)));
  g->number_of_vertices = number_of_vertices;

  //making elements of all head null i.e.,
  //their data -1 and next null
  int i;
  for(i=0; i<number_of_vertices; i++) {
    node *z = new_node(-1); //*z is pointer of node. z stores address of node
    g->heads[i] = *z; //*z is the value at the address z
  }

  return g;
}

// function to add new node to graph
void add_node_to_graph(graph *g, int data) {
  // creating a new node;
  node *z = new_node(data);
  //this node will be added into the heads array of the graph g
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    // we will add node when the data in the node is -1
    if (g->heads[i].data < 0) {
      g->heads[i] = *z; //*z is the value at the address z
      break; //node is added
    }
  }
}

// function to check of the node is in the head array of graph or not
int in_graph_head_list(graph *g, int data) {
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    if(g->heads[i].data == data)
      return 1;
  }
  return 0;
}

// function to add edge
void add_edge(graph *g, int source, int dest) {
  //if source or edge is not in the graph, add it
  if(!in_graph_head_list(g, source)) {
    add_node_to_graph(g, source);
  }
  if(!in_graph_head_list(g, dest)) {
    add_node_to_graph(g, dest);
  }

  int i,j;
  // iterating over heads array to find the source node
  for(i=0; i<g->number_of_vertices; i++) {
    if(g->heads[i].data == source) { //source node found

      int dest_index; //index of destination element in array heads
      // iterating over heads array to find node containg destination element
      for(j=0; j<g->number_of_vertices; j++) {
        if(g->heads[j].data == dest) { //destination found
          dest_index = j;
          break;
        }
      }

      list_node *n = new_list_node(dest_index); // new adjacency list node with destination index
      if (g->heads[i].head == NULL) { // no head, first element in adjaceny list
        g->heads[i].head = n;
      }
      else { // there is head which is pointer by the node in the head array
        list_node *temp;
        temp = g->heads[i].head;

        // iterating over adjaceny list to insert new list_node at last
        while(temp->next != NULL) {
          temp = temp->next;
        }
        temp->next = n;
      }
      break;
    }
  }
}

void print_graph(graph *g) {
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    list_node *temp;
    temp = g->heads[i].head;
    printf("%d\t",g->heads[i].data);
    while(temp != NULL) {
      printf("%d\t",g->heads[temp->index_of_item].data);
      temp = temp->next;
    }
    printf("\n");
  }
}

typedef struct queue_node {
  node *n;
  struct queue_node *next;
}queue_node;

struct queue
{
    int count;
    queue_node *front;
    queue_node *rear;
};
typedef struct queue queue;

int is_empty_queue(queue *q)
{
  return !(q->count);
}

void enqueue(queue *q, node *n)
{
  queue_node *new_queue_node;
  new_queue_node = malloc(sizeof(queue_node));
  new_queue_node->n = n;
  new_queue_node->next = NULL;
  if(!is_empty_queue(q))
  {
    q->rear->next = new_queue_node;
    q->rear = new_queue_node;
  }
  else
  {
    q->front = q->rear = new_queue_node;
  }
  q->count++;
}

queue_node* dequeue(queue *q)
{
  queue_node *tmp;
  tmp = q->front;
  q->front = q->front->next;
  q->count--;
  return tmp;
}

queue* make_queue()
{
  queue *q;
  q = malloc(sizeof(queue));
  q->count = 0;
  q->front = NULL;
  q->rear = NULL;
  return q;
}

void print_queue(queue *q) {
  queue_node *tmp;
  tmp = q->front;
  while(tmp != NULL) {
    printf("%d\t",tmp->n->data);
    tmp = tmp->next;
  }
  printf("\n");
}

void bfs(graph *g) {
  //here, we are using first node as source
  node s = g->heads[0];
  int i;
  for(i=0; i<g->number_of_vertices; i++) {
    g->heads[i].colr = White;
  }
  s.colr = Gray;

  queue* q = make_queue();
  enqueue(q, &s);

  while(!is_empty_queue(q)) {
    // print_queue(q);
    queue_node *u = dequeue(q);
    list_node *temp;
    temp = u->n->head;
    while(temp != NULL) {
      if (g->heads[temp->index_of_item].colr == White) {
        g->heads[temp->index_of_item].colr = Gray;
        enqueue(q, &g->heads[temp->index_of_item]);
      }
      temp = temp->next;
    }
    u->n->colr = Black;
    printf("%d\n",u->n->data);
  }
}

int main() {
  graph *g = new_graph(7);
  add_edge(g, 1, 2);
  add_edge(g, 1, 5);
  add_edge(g, 1, 3);
  add_edge(g, 2, 6);
  add_edge(g, 2, 4);
  add_edge(g, 5, 4);
  add_edge(g, 3, 4);
  add_edge(g, 3, 7);
  bfs(g);
  return 0;
}
from graph_directed import Graph #importing graph from previous chapter but directed version
from graph_directed import Node #see code of previous chapter
from graph_directed import Color

q = [] #queue for BFS

def enqueue(n):
    global q
    q = [n]+q

def dequeue():
    global q
    temp = q[len(q)-1]
    del(q[len(q)-1])
    return temp

def bfs(g):
    s = g.heads[0]

    for i in range(0, g.number_of_vertices):
        g.heads[i].color = Color.White
    s.color = Color.Gray

    enqueue(s)

    while(len(q)>0):
        u = dequeue()
        temp = u.head
        while(temp != None):
            if(g.heads[temp.index_of_item].color == Color.White):
                g.heads[temp.index_of_item].color = Color.Gray
                enqueue(g.heads[temp.index_of_item])
            temp = temp.next
        u.color = Color.Black
        print(u.data)

if __name__ == '__main__':
    g = Graph(7)

    g.add_edge(1, 2)
    g.add_edge(1, 5)
    g.add_edge(1, 3)
    g.add_edge(2, 6)
    g.add_edge(2, 4)
    g.add_edge(5, 4)
    g.add_edge(3, 4)
    g.add_edge(3, 7)

    bfs(g)
/*
  Node for linked list of adjacent elements.
  This will contain a pointer for next node.
  It will not contain the real element but the index of
  element of the array containing all the vertices V.
*/
class ListNode {
  private int indexOfItem;
  private ListNode next;

  public ListNode(int itemIndex) {
    indexOfItem = itemIndex;
    next = null;
  }

  public ListNode getNext() {
    return next;
  }

  public void setNext(ListNode n) {
    next = n;
  }

  public int getIndexOfItem() {
    return indexOfItem;
  }
}

/*
  Node to store the real element.
  Contain data and pointer to the
  first element (head) of the adjacency list.
*/
class Node {
  public static enum Color {
    White,
    Black,
    Gray
  }

  private int data;
  private Color color;
  private ListNode head;

  public Node(int d) {
    data = d;
    head = null;
    color = Color.White;
  }

  public int getData() {
    return data;
  }

  public ListNode getHead() {
    return head;
  }

  public void setHead(ListNode n) {
    head = n;
  }

  public Color getColor() {
    return color;
  }

  public void setColor(Color c) {
    color = c;
  }
}

/*
  Graph will contain number of vertices and
  an array containing all the nodes (V).
*/
class Graph {
  private int numberOfVertices;
  private Node[] heads;
  /*
  array heads      Adjacency list. contain index and next
  contain data
  and head of
  adjacency list
   ____            ____    ____    ____
  |node|    ----> |list|->|    |->|    |
  |____|          |node|  |____|  |____|
   ____            ____    ____    ____
  |    |    ----> |    |->|    |->|    |
  |____|          |____|  |____|  |____|
   ____            ____    ____    ____
  |    |    ----> |    |->|    |->|    |
  |____|          |____|  |____|  |____|
   ____            ____    ____    ____
  |    |    ----> |    |->|    |->|    |
  |____|          |____|  |____|  |____|

  */

  public Graph(int noOfVertices) {
    numberOfVertices = noOfVertices;
    heads = new Node[numberOfVertices];

    //making elements of all head null i.e.,
    //their data -1 and next null
    for(int i=0; i<numberOfVertices; i++) {
      Node z = new Node(-1); //*z is pointer of node. z stores address of node
      heads[i] = z; //*z is the value at the address z
    }
  }

  public Node[] getHeads() {
    return heads;
  }

  public int getNumberOfVertices() {
    return numberOfVertices;
  }

  // method to add new node to graph
  public void addNodeToGraph(int data) {
    // creating a new node;
    Node z = new Node(data);
    //this node will be added into the heads array of the graph g
    for(int i=0; i<numberOfVertices; i++) {
      // we will add node when the data in the node is -1
      if(heads[i].getData() < 0) {
        heads[i] = z; //*z is the value at the address z
        break; //node is added
      }
    }
  }

  // function to check of the data is in the head array of graph or not
  public boolean inGraphHeadList(int data) {
    for(int i=0; i<numberOfVertices; i++) {
      if(heads[i].getData() == data)
        return true;
      }
      return false;
  }

  // function to add edge
  public void addEdge(int source, int dest) {
    //if source or edge is not in the graph, add it
    if(!inGraphHeadList(source)) {
      addNodeToGraph(source);
    }
    if(!inGraphHeadList(dest)) {
      addNodeToGraph(dest);
    }

    // iterating over heads array to find the source node
    for(int i=0; i<numberOfVertices; i++) {
      if(heads[i].getData() == source) { //source node found

        int destIndex=0; //index of destination element in array heads

        // iterating over heads array to find node containg destination element
        for(int j=0; j<numberOfVertices; j++) {
          if(heads[j].getData() == dest) { //destination found
            destIndex = j;
            break;
          }
        }

        ListNode n = new ListNode(destIndex); // new adjacency list node with destination index
        if(heads[i].getHead() == null) { // no head, first element in adjaceny list
          heads[i].setHead(n);
        }
        else { // there is head which is pointer by the node in the head array
          ListNode temp;
          temp = heads[i].getHead();

          // iterating over adjaceny list to insert new list_node at last
          while(temp.getNext() != null) {
            temp = temp.getNext();
          }
          temp.setNext(n);
        }
        break;
      }
    }
  }

  public void printGraph() {
    for(int i=0; i<numberOfVertices; i++) {
      ListNode temp;
      temp = heads[i].getHead();
      System.out.print(heads[i].getData()+"\t");
      while(temp != null) {
        System.out.print(heads[temp.getIndexOfItem()].getData()+"\t");
        temp = temp.getNext();
      }
      System.out.println("");
    }
  }
}

class QueueNode {
  private Node n;
  private QueueNode next;

  public QueueNode(Node node) {
    n = node;
    next = null;
  }

  public void setNext(QueueNode n) {
    next = n;
  }

  public QueueNode getNext() {
    return next;
  }

  public Node getNode() {
    return n;
  }
}

class Queue {
  private int count;
  private QueueNode front;
  private QueueNode rear;

  public Queue() {
    count = 0;
    rear = null;
    front = null;
  }

  public boolean isEmpty() {
    if(count == 0)
      return true;
    return false;
  }

  public void enqueue(Node n) {
    QueueNode newQueueNode = new QueueNode(n);

    if(!isEmpty()) {
      rear.setNext(newQueueNode);
      rear = newQueueNode;
    }
    else {
      front = rear = newQueueNode;
    }
    count++;
  }

  public QueueNode dequeue() {
    QueueNode temp;
    temp = front;
    front = front.getNext();
    count--;
    return temp;
  }

  public void printQueue() {
    QueueNode temp;
    temp = front;
    while(temp != null) {
      System.out.print(temp.getNode().getData()+"\t");
      temp = temp.getNext();
    }
    System.out.println("");
  }
}

class BFS {

  public static void bfs(Graph g) {
    //here, we are using first node as source
    Node s = g.getHeads()[0];

    for(int i=0; i<g.getNumberOfVertices(); i++) {
      g.getHeads()[i].setColor(Node.Color.White);
    }
    s.setColor(Node.Color.Gray);

    Queue q = new Queue();
    q.enqueue(s);

    while(!q.isEmpty()) {
      // q.printQueue();
      QueueNode u = q.dequeue();
      ListNode temp;

      temp = u.getNode().getHead();
      while(temp != null) {
        if(g.getHeads()[temp.getIndexOfItem()].getColor() == Node.Color.White) {
          g.getHeads()[temp.getIndexOfItem()].setColor(Node.Color.Gray);
          q.enqueue(g.getHeads()[temp.getIndexOfItem()]);
        }
        temp = temp.getNext();
      }
      u.getNode().setColor(Node.Color.Black);
      System.out.println(u.getNode().getData());
    }
  }

  public static void main(String[] args) {
    Graph g = new Graph(7);

    g.addEdge(1, 2);
    g.addEdge(1, 5);
    g.addEdge(1, 3);
    g.addEdge(2, 6);
    g.addEdge(2, 4);
    g.addEdge(5, 4);
    g.addEdge(3, 4);
    g.addEdge(3, 7);

    bfs(g);
  }
}

BFS has also an interesting feature that it stores the shortest path of nodes from the source from where we start our search. Thus, if we store the distance at which the nodes are first discovered then that gives us the shortest path of the corresponding nodes from a source.

shortest path in bfs

We can also store a property distance along with its color for each node to accomplish this. Now, suppose we are given a node and we need to print the shortest path from the source s.

The easiest way of doing this would be to also store the parent of each node i.e., the node from which it was discovered first.

storing parent in bfs

We can easily trace the parent of the node to get back to the source and find the shortest path.

BFS-MODIFIED(G, s)
  for i in G.V
    i.color = white
    i.distance  = infinite // initially, we don't have any path to reach
    i.parent = NULL
  s.color = gray
  s.distance = 0 // distance of source is 0
  s.parent = NULL // source has no parent

  queue.enqueue(s)

  while q not empty
    u = queue.dequeue()
    for i in Adj[u]
      if i.color == white // only if the node is not yet discovered
        i.color = gray // mark it discovered
        i.distance = u.distance+1 // distance of the adjacent node is one more than its parent
        i.parent = u
        queue.enqueue(i)
    u.color = black // all adjacent nodes of this node are discovered

Now, we can easily trace the parent of the nodes to print the shortest path.

tracing parent in bfs

We will just trace the parent until the source node is reached but if we reach any node whose parent is NULL, then there isn't any path from that node to the source.

PRINT-PATH(G, s, n)
  if n == s
    print s
  else if n == NULL
    print "NO path"
  else
    PRINT-PATH(G, s, n.parent)
    print n

Analysis of BFS


We have already seen that we are enqueuing and dequeuing each vertex only once and the enqueue and dequeue operations are constant time taking operations ($O(1)$), so the total time taken for enqueue and dequeue is $O(|V|)$. We are also scanning all the adjacency lists of all the node and we have discussed that they are of $\Theta(|E|)$ in number. So, this will take $O(|E|)$ time and thus, the total time for BFS will be $O(|V|+|E|)$.

Depth-first search is also a searching technique used with the graphs which we are going to learn in the next chapter.

Books are as useful to a stupid person as a mirror is useful to a blind person.
- Chanakya


Ask Yours
Post Yours
Doubt? Ask question