Breadth First Search in Data Structure

Just like DFS, BFS (Breadth-first Search ) is also a recursive traversal algorithm for searching all vertices of the graph or tree data structure. In this article, we will learn about BFS, its implementation, and its applications.

Breadth First Search

BFS Algorithms start from the root node and explores all the neighboring nodes. In the next step, it selects the nearest node and explores it. Since graphs may contain cycles, BFS ensures each node is visited exactly once.

• BFS uses Queue as its backend data structure.
• Edges that lead to an unvisited node are called discovery edges while the edges that lead to an already visited node are called block edges.

Breadth First Search Procedure

BFS implementation categorizes the vertices in the graphs into two categories:

• Visited
• Not visited

The major objective is to visit each node and keep marking them as “visited” and ensuring that each node is visited exactly once and no cycle is formed.

Steps for BFS algorithm

1. Start by inserting the starting vertex of the graph into the rear end of the queue.
2. remove the item from the front of the queue and add it to the visited list
3. Create the adjacency list for that vertex. Add the non-visited nodes in the list at the rear end of the queue
4. Keep repeating steps 2 and 3 until the queue is empty

Breadth-First Search Algorithm

Step 1: SET STATUS = 1 for each node in graph G
Step 2: Enqueue the starting node A and set STATUS = 2
Step 3: Repeat Steps 4 and 5 until the QUEUE is empty
Step 4: Dequeue a node N. Set its STATUS = 3
Step 5: Enqueue all the neighbors of N with STATUS = 1 and set their STATUS = 2
[END OF LOOP]
Step 6: EXIT

Working of Breadth First Search

Let us consider the graph below:

Starting node: A

Step 1: Create an adjacency list for the above graph.

Step 2: Create an empty queue.

Step 3: Enqueue ‘A’ into the queue

Step 4: Dequeue ‘A’ and Enqueue ‘F’ and ‘B’. Mark node ‘A’ as the visited node

Step 5: Dequeue ‘F’ and Enqueue ‘D’. Mark ‘F’ as a visited node.

Step 6: Dequeue ‘B’ and Enqueue ‘C’. Mark ‘B’ as a visited node.

Step 7: Dequeue ‘D’ and Enqueue ‘E’. Mark ‘D’ as a visited node.

Step 8: Dequeue ‘C’ and ‘E’. Mark ‘C’ and ‘E’ as a visited node. No new node is left.

implementation of Breadth First Search in C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue 
{
  int items[SIZE];
  int front;
  int rear;
};

struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node 
{
  int vertex;
  struct node* next;
};

struct node* createNode(int);

struct Graph 
{
  int numVertices;
  struct node** adjLists;
  int* visited;
};

void bfs(struct Graph* graph, int startNode) 
{
  struct queue* q = createQueue();

  graph->visited[startNode] = 1;
  enqueue(q, startNode);

  while (!isEmpty(q)) 
  {
    printQueue(q);
    int currentNode = dequeue(q);
    printf("Visited %d\n", currentNode);

    struct node* temp = graph->adjLists[currentNode];

    while (temp) 
    {
      int adjVertex = temp->vertex;

      if (graph->visited[adjVertex] == 0) 
      {
        graph->visited[adjVertex] = 1;
        enqueue(q, adjVertex);
      }
      temp = temp->next;
    }
  }
}

struct node* createNode(int ver) 
{
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = ver;
  newNode->next = NULL;
  return newNode;
}

struct Graph* createGraph(int vertices) 
{
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));
  graph->visited = malloc(vertices * sizeof(int));

  int i;
  for (i = 0; i < vertices; i++) 
  {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }

  return graph;
}

void addEdge(struct Graph* graph, int s_node, int d_node) 
{
  struct node* newNode = createNode(d_node);
  newNode->next = graph->adjLists[s_node];
  graph->adjLists[s_node] = newNode;

  newNode = createNode(s_node);
  newNode->next = graph->adjLists[d_node];
  graph->adjLists[d_node] = newNode;
}

struct queue* createQueue() 
{
  struct queue* q = malloc(sizeof(struct queue));
  q->front = -1;
  q->rear = -1;
  return q;
}

int isEmpty(struct queue* q) 
{
  if (q->rear == -1)
    return 1;
  else
    return 0;
}

void enqueue(struct queue* q, int val) 
{
  if (q->rear == SIZE - 1)
    printf("\nQueue is Full!!");
  else {
    if (q->front == -1)
      q->front = 0;
    q->rear++;
    q->items[q->rear] = val;
  }
}

int dequeue(struct queue* q) 
{
  int item;
  if (isEmpty(q)) 
  {
    printf("Queue is empty");
    item = -1;
  } 
  else 
  {
    item = q->items[q->front];
    q->front++;
    if (q->front > q->rear) 
    {
      q->front = q->rear = -1;
    }
  }
  return item;
}

void printQueue(struct queue* q) 
{
  int i = q->front;

  if (isEmpty(q))
  {
    printf("Queue empty");
  } 
  else 
  {
    printf("\n current Queue \n");
    for (i = q->front; i < q->rear + 1; i++) 
    {
      printf("%d ", q->items[i]);
    }
  }
}

int main() 
{
  struct Graph* graph = createGraph(6);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 0, 3);
  addEdge(graph, 1, 2);
  addEdge(graph, 1, 3);
  addEdge(graph, 2, 4);
  addEdge(graph, 3, 4);

  bfs(graph, 0);

  return 0;
}

BFS implementation in C++

#include <iostream>
#include <list>
using namespace std;

class BFSGraph 
{
  int numVertices;
  list<int>* adjLists;
  bool* visited;

   public:
  BFSGraph(int vertices);
  void addEdge(int src, int dest);
  void BFS(int startVertex);
};

BFSGraph::BFSGraph(int vertices) 
{
  numVertices = vertices;
  adjLists = new list<int>[vertices];
}

void BFSGraph::addEdge(int s_node, int d_node) 
{
  adjLists[s_node].push_back(d_node);
  adjLists[d_node].push_back(s_node);
}

void BFSGraph::BFS(int startVertex) 
{
  visited = new bool[numVertices];
  for (int i = 0; i < numVertices; i++)
    visited[i] = false;

  list<int> queue;

  visited[startVertex] = true;
  queue.push_back(startVertex);

  list<int>::iterator i;

  while (!queue.empty())
  {
    int currentVertex = queue.front();
    cout << "Visited " << currentVertex << "\n";
    queue.pop_front();

    for (i = adjLists[currentVertex].begin(); i != adjLists[currentVertex].end(); ++i) 
    {
      int adjVertex = *i;
      if (!visited[adjVertex]) 
      {
        visited[adjVertex] = true;
        queue.push_back(adjVertex);
      }
    }
  }
}

int main() 
{
  BFSGraph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(0, 3);
  g.addEdge(2, 0);
  g.addEdge(2, 1);
  g.addEdge(3, 3);
  g.addEdge(3, 1);

  g.BFS(2);

  return 0;
}

Implementation of BFS in JAVA

import java.util.*;

public class BFSGraph 
{
  private int V;
  private LinkedList<Integer> adj[];

  BFSGraph(int v) 
  {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adj[i] = new LinkedList();
  }

  void addEdge(int v, int w) 
  {
    adj[v].add(w);
  }

  void BFS(int s) 
  {

    boolean visited[] = new boolean[V];

    LinkedList<Integer> queue = new LinkedList();

    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) 
    {
      s = queue.poll();
      System.out.print(s + " ");

      Iterator<Integer> i = adj[s].listIterator();
      while (i.hasNext()) 
      {
        int n = i.next();
        if (!visited[n]) 
        {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }

  public static void main(String args[]) 
  {
    BFSGraph g = new BFSGraph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(2, 1);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.addEdge(3, 0);

    System.out.println("Breadth First Traversal ");

    g.BFS(2);
  }
}

BFS implementation in python

import collections

def bfs(graph, root):

    visited, queue = set(), collections.deque([root])
    visited.add(root)

    while queue:

        ver = queue.popleft()
        print(str(ver) + " ", end="")

        for near in graph[ver]:
            if near not in visited:
                visited.add(near)
                queue.append(near)


if __name__ == '__main__':
    graph = {0: [1, 2], 1: [2,0], 2: [3], 3: [1, 2]}
    print("Breadth First Traversal: ")
    bfs(graph, 1)

Complexity of Breadth-First Search

The time complexity of DFS is represented in the form O(V+E) where V is the number of vertices and E is the number of edges.

The space complexity of DFS algorithms is O(V).

Applications of BFS

BFS Algorithm is used in

1. Pathfinding algorithms
2. GPS Navigation
3. Minimum spanning trees
4. Building index by search index
5. Ford Fulkerson algorithm. Finds maximum flow in a network
6. Detection of a cycle in an undirected graph

Conclusion

With this article, the graph data structure is complete. We now have a complete understanding of the Graphs in Data structures and their different representation in form of an adjacency list and an adjacency matrix.

In other articles, we have seen traversal algorithms for finding a node in the graph or tree and its implementation in different programming languages. In future articles, we will learn about the tree data structures and everything related to them.