Algorithm


Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level. It starts at the source node and explores all its neighbors before moving on to the next level of neighbors. BFS is commonly used to find the shortest path in an unweighted graph and is also useful for various other applications.

Here's a high-level description of the BFS algorithm:

  1. Initialization:

    • Enqueue the source node into a queue.
    • Mark the source node as visited.
  2. Exploration:

    • While the queue is not empty:
      • Dequeue a node from the front of the queue.
      • Explore all unvisited neighbors of the dequeued node.
      • Enqueue each unvisited neighbor into the queue and mark it as visited.
  3. Termination:

    • Repeat step 2 until the queue is empty.

BFS is often implemented using a queue data structure. The order in which nodes are visited is important, as it ensures that nodes closer to the source are visited before nodes farther away. This leads to finding the shortest path in an unweighted graph.

 

Code Examples

#1 Breadth first search implement in Python

Code - Python Programming

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            print(vertex, end=' ')
            visited.add(vertex)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

# Example usage:
# Define an adjacency list representation of a graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F', 'G'],
    'D': ['B'],
    'E': ['B', 'H'],
    'F': ['C'],
    'G': ['C'],
    'H': ['E']
}

# Start BFS from the 'A' vertex
print("BFS starting from 'A':")
bfs(graph, 'A')
Copy The Code & Try With Live Editor

#2 Breadth first search implement in Java

Code - Java Programming

import java.util.LinkedList;
import java.util.Queue;

public class BFSExample {

    static class Graph {
        private int V; // Number of vertices
        private LinkedList < Integer>[] adj; // Adjacency list

        // Constructor
        Graph(int v) {
            V = v;
            adj = new LinkedList[v];
            for (int i = 0; i  <  v; ++i) {
                adj[i] = new LinkedList<>();
            }
        }

        // Add an edge to the graph
        void addEdge(int v, int w) {
            adj[v].add(w);
        }

        // Breadth-First Search starting from a given source vertex
        void BFS(int s) {
            // Mark all the vertices as not visited
            boolean[] visited = new boolean[V];

            // Create a queue for BFS
            Queue < Integer> queue = new LinkedList<>();

            // Mark the current node as visited and enqueue it
            visited[s] = true;
            queue.add(s);

            while (!queue.isEmpty()) {
                // Dequeue a vertex from the queue and print it
                s = queue.poll();
                System.out.print(s + " ");

                // Get all adjacent vertices of the dequeued vertex s
                // If an adjacent vertex has not been visited, mark it visited and enqueue it
                for (Integer neighbor : adj[s]) {
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue.add(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        // Create a sample graph
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("Breadth First Traversal (starting from vertex 2): ");
        graph.BFS(2);
    }
}
Copy The Code & Try With Live Editor

#3 Breadth first search implement in C

Code - C Programming

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// Structure to represent a queue
struct Queue {
    int items[MAX_SIZE];
    int front;
    int rear;
};

// Function to initialize a queue
struct Queue* createQueue() {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return queue->front == -1;
}

// Function to add an element to the queue
void enqueue(struct Queue* queue, int value) {
    if (queue->rear == MAX_SIZE - 1) {
        printf("Queue is full\n");
    } else {
        if (queue->front == -1) {
            queue->front = 0;
        }
        queue->rear++;
        queue->items[queue->rear] = value;
    }
}

// Function to remove an element from the queue
int dequeue(struct Queue* queue) {
    int item;
    if (isEmpty(queue)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        item = queue->items[queue->front];
        queue->front++;
        if (queue->front > queue->rear) {
            queue->front = queue->rear = -1;
        }
        return item;
    }
}

// Function to perform Breadth-First Search
void BFS(int graph[][MAX_SIZE], int vertices, int start) {
    struct Queue* queue = createQueue();
    int visited[MAX_SIZE] = {0}; // Array to keep track of visited vertices

    printf("Breadth-First Search starting from vertex %d:\n", start);

    visited[start] = 1; // Mark the start vertex as visited
    enqueue(queue, start);

    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("%d ", currentVertex);

        for (int i = 0; i  <  vertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                enqueue(queue, i);
            }
        }
    }

    printf("\n");
}

int main() {
    int vertices, start;

    printf("Enter the number of vertices: ");
    scanf("%d", &vertices);

    int graph[MAX_SIZE][MAX_SIZE];

    printf("Enter the adjacency matrix:\n");
    for (int i = 0; i  <  vertices; i++) {
        for (int j = 0; j  <  vertices; j++) {
            scanf("%d", &graph[i][j]);
        }
    }

    printf("Enter the starting vertex: ");
    scanf("%d", &start);

    BFS(graph, vertices, start);

    return 0;
}
Copy The Code & Try With Live Editor

#4 Breadth first search implement in C++

Code - C++ Programming

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class Graph {
public:
    Graph(int vertices);
    void addEdge(int v, int w);
    void BFS(int startVertex);

private:
    int vertices;
    vector < vector<int>> adjList;
};

Graph::Graph(int vertices) : vertices(vertices) {
    adjList.resize(vertices);
}

void Graph::addEdge(int v, int w) {
    adjList[v].push_back(w);
}

void Graph::BFS(int startVertex) {
    vector < bool> visited(vertices, false);
    queue<int> q;

    visited[startVertex] = true;
    q.push(startVertex);

    while (!q.empty()) {
        int currentVertex = q.front();
        cout << currentVertex << " ";
        q.pop();

        for (int adjacentVertex : adjList[currentVertex]) {
            if (!visited[adjacentVertex]) {
                visited[adjacentVertex] = true;
                q.push(adjacentVertex);
            }
        }
    }
}

int main() {
    Graph g(6); // Create a graph with 6 vertices

    // Add edges to the graph
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 4);
    g.addEdge(3, 5);
    g.addEdge(4, 5);

    cout << "Breadth-First Search starting from vertex 0:" << endl;
    g.BFS(0);

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Breadth first search Data Structure and Algorithm