Johnnn

Let's go

Exploring the Breadth-First Search Algorithm in Graphs: A Comprehensive Guide

by · Published · Updated

Graphs are powerful data structures that model relationships between entities. When analyzing graphs, traversing them efficiently becomes essential. One of the fundamental graph traversal algorithms is the Breadth-First Search (BFS). In this blog post, we will delve into the inner workings of BFS, understand its algorithmic approach, analyze its time complexity, and provide code examples in C, C++, Python, and Java.

Understanding the Breadth-First Search Algorithm:
BFS is an algorithm used to explore or traverse a graph in a systematic manner. It starts at a given vertex (or node) and explores all its neighboring vertices before moving on to the next level of vertices. The algorithm proceeds in a breadth-first manner, exploring the nearest vertices before moving deeper into the graph.

BFS Algorithm Steps:

  1. Create a queue to store vertices to be visited.
  2. Initialize a visited array to keep track of visited vertices.
  3. Enqueue the starting vertex and mark it as visited.
  4. While the queue is not empty, do the following:
    a. Dequeue a vertex from the queue.
    b. Process the dequeued vertex (e.g., print it or perform required operations).
    c. Enqueue all unvisited neighbors of the dequeued vertex.
    d. Mark the dequeued vertex as visited.
  5. Repeat steps 4a to 4d until the queue is empty.

Time Complexity of BFS:
The time complexity of BFS is O(V + E), where V represents the number of vertices and E represents the number of edges in the graph. This complexity arises from visiting each vertex once and each edge once during the traversal.

Example Graph and Traversal:
Let’s consider the following graph to demonstrate the BFS algorithm:

     A
   /   \
  B     C
 / \   /  \
D   E F    G

Starting with vertex A, the traversal would be: A, B, C, D, E, F, G.

Code Examples in C, C++, Python, and Java:

  1. C:
#include<stdio.h>
#include<stdlib.h>

#define MAX_VERTICES 100

// Structure to represent a graph node
struct Node {
    int value;
    struct Node* next;
};

// Function to create a new graph node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}

// Function to add an edge between two nodes
void addEdge(struct Node* adjacencyList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjacencyList[src];
    adjacencyList[src] = newNode;

    newNode = createNode(src);
    newNode->next = adjacencyList[dest];
    adjacencyList[dest] = newNode;
}

// Function to perform breadth-first search
void BFS(struct Node* adjacencyList[], int startVertex, int visited[]) {
    struct Node* currentNode;
    int i;
    int queue[MAX_VERTICES];
    int front = 0, rear = -1;

    visited[startVertex] = 1;
    queue[++rear] = startVertex;

    while (front <= rear) {
        int vertex = queue[front++];

        printf("%d ", vertex);

        currentNode = adjacencyList[vertex];

        while (currentNode) {
            int neighbor = currentNode->value;

            if (!visited[neighbor]) {
                queue[++rear] = neighbor;
                visited[neighbor] = 1;
            }

            currentNode = currentNode->next;
        }
    }
}

int main() {
    int numVertices = 7;
    struct Node* adjacencyList[MAX_VERTICES] = { NULL };

    addEdge(adjacencyList, 0, 1);
    addEdge(adjacencyList, 0, 2);
    addEdge(adjacencyList, 1, 3);
    addEdge(adjacencyList, 1, 4);
    addEdge(adjacencyList, 2, 5);
    addEdge(adjacencyList, 2, 6);

    int visited[MAX_VERTICES] = { 0 };
    printf("BFS Traversal: ");
    BFS(adjacencyList, 0, visited);

    return 0;
}
  1. C++:
#include<iostream>
#include<queue>
#include<vector>
using namespace std;

// Function to perform breadth-first search
void BFS(vector<vector<int>>& adjacencyList, int startVertex, vector<int>& visited) {
    queue<int> q;
    visited[startVertex] = 1;
    q.push(startVertex);

    while (!q.empty()) {
        int vertex = q.front();
        q.pop();

        cout << vertex << " ";

        for (int neighbor : adjacencyList[vertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = 1;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int numVertices = 7;
    vector<vector<int>> adjacencyList(numVertices);

    adjacencyList[0].push_back(1);
    adjacencyList[0].push_back(2);
    adjacencyList[1].push_back(3);
    adjacencyList[1].push_back(4);
    adjacencyList[2].push_back(5);
    adjacencyList[2].push_back(6);

    vector<int> visited(numVertices, 0);
    cout << "BFS Traversal: ";
    BFS(adjacencyList, 0, visited);

    return 0;
}
  1. Python:
from collections import deque

# Function to perform breadth-first search
def BFS(adjacencyList, startVertex, visited):
    queue = deque()
    visited[startVertex] = 1
    queue.append(startVertex)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in adjacencyList[vertex]:
            if not visited[neighbor]:
                visited[neighbor] = 1
                queue.append(neighbor)

# Number of vertices
numVertices = 7

# Creating the adjacency list
adjacencyList = [[] for _ in range(numVertices)]

# Adding edges to the graph
adjacencyList[0].extend([1, 2])
adjacencyList[1].extend([3, 4])
adjacencyList[2].extend([5, 6])

# Initializing visited array
visited = [0] * numVertices

print("BFS Traversal:", end=" ")
BFS(adjacencyList, 0, visited)
  1. Java:
import java.util.*;

class Graph {
    private int numVertices;
    private LinkedList<Integer>[] adjacencyList;

    Graph(int numVertices) {
        this.numVertices = numVertices;
        adjacencyList = new LinkedList[numVertices];
        for (int i = 0; i < numVertices; ++i)
            adjacencyList[i] = new LinkedList();
    }

    void addEdge(int src, int dest) {
        adjacencyList[src].add(dest);
        adjacencyList[dest].add(src);
    }

    void BFS(int startVertex) {
        boolean[] visited = new boolean[numVertices];
        LinkedList<Integer> queue = new LinkedList<>();
        visited[startVertex] = true;
       queue.add(startVertex);

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

            Iterator<Integer> iterator = adjacencyList[vertex].listIterator();
            while (iterator.hasNext()) {
                int neighbor = iterator.next();
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }

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

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
        graph.addEdge(2, 6);

        System.out.print("BFS Traversal: ");
        graph.BFS(0);
    }
}

Conclusion:
Breadth-First Search (BFS) is a versatile algorithm for traversing graphs. By employing a queue and visiting vertices in a breadth-first manner, it allows us to explore and process the graph efficiently. In this blog post, we have covered the BFS algorithm’s steps, analyzed its time complexity, and provided code examples in C, C++, Python, and Java. Understanding BFS is crucial for various graph-based applications, such as finding the shortest path, connected components, and more.

You may also like...