Breadth First Search BFS

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level, visiting all the neighbours of a vertex before moving on to the next level. It is often used to find the shortest path between two vertices in an unweighted graph.

Algorithm:

BFS uses a queue data structure to keep track of the vertices to be visited. The algorithm operates as follows:

1. Initialization:

   • Create a boolean array to mark visited vertices.
   • Initialize all vertices as not visited.
   • Enqueue the starting vertex and mark it as visited.

2. BFS Traversal:

• While the queue is not empty:
• Dequeue a vertex from the front of the queue.
• Process the dequeued vertex (print or perform any other operation).
• Enqueue all unvisited neighbors of the dequeued vertex and mark them as visited.

pseudocode-BFS

procedure BFS(startVertex):

    create a queue

    enqueue startVertex

    mark startVertex as visited

    while the queue is not empty:

        currentVertex = dequeue from the queue

        process currentVertex (print or perform an operation)

        for each neighbour of currentVertex:

            if neighbour is not visited:

                enqueue neighbour

                mark neighbour as visited

Description:

• Queue:

  • BFS uses a first-in, first-out (FIFO) queue to keep track of the vertices to visit. This ensures that vertices are visited in the order they are discovered.

• Visited Array:

  • A boolean array is maintained to mark whether a vertex has been visited or not. This prevents revisiting vertices and infinite loops.

• Shortest Path:

  • BFS explores the graph level by level, so if the graph is unweighted, the first time a vertex is visited, it is reached by the shortest path.

• Connected Components:

• BFS can be used to find connected components in an undirected graph. If the graph is disconnected, the algorithm is applied to unvisited vertices to find additional connected components.
• 
  

Example:

Let's see how the Breadth First Search algorithm works with an example. We use an undirected graph with 5 vertices.

We start from vertex 0, the BFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the Queue.

Next, we visit the element at the front of queue i.e. 1 and go to its adjacent nodes. Since 0 has already been visited, we visit 2 instead.

Vertex 2 has an unvisited adjacent vertex in 4, so we add that to the back of the queue and visit 3, which is at the front of the queue.

Only 4 remains in the queue since the only adjacent node of 3 i.e. 0 is already visited. We visit it.

Time Complexity:

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

Space Complexity:

The space complexity of BFS is O(V), where V is the number of vertices. This is due to the space required for the queue and the visited array.

Applications:

Shortest Path Finding
Network Broadcasting
Connected Components
Web Crawling
Puzzle Solving:
Geographical Mapping

C Program- BFS

/******************************************/

#include <stdio.h>

#include <stdlib.h>

#define MAX_VERTICES 10

// Function to perform Breadth-First Search (BFS)

void bfs(int startVertex, int visited[MAX_VERTICES], int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {

    // Create a queue for BFS

    int queue[MAX_VERTICES];

    int front = -1, rear = -1;

    // Enqueue the startVertex

    queue[++rear] = startVertex;

    visited[startVertex] = 1;

    while (front != rear) {

        // Dequeue a vertex from the front of the queue

        int currentVertex = queue[++front];

        printf("V%d ", currentVertex ); // Assuming vertex labels are 'V0', 'V1', 'V2', ...

        // Enqueue all unvisited neighbors

        for (int i = 0; i < numVertices; i++) {

            if (adjacencyMatrix[currentVertex][i] == 1 && !visited[i]) {

                queue[++rear] = i;

                visited[i] = 1;

            }

        }

    }

}

int main() {

    int numVertices, i, j;

    printf("Enter the number of vertices (max %d): ", MAX_VERTICES);

    scanf("%d", &numVertices);

    // Input the adjacency matrix

    int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

    printf("Enter the adjacency matrix (1 for connected, 0 for not connected):\n");

    for (i = 0; i < numVertices; i++) {

        for (j = 0; j < numVertices; j++) {

            scanf("%d", &adjacencyMatrix[i][j]);

        }

    }

    // Array to keep track of visited vertices

    int visited[MAX_VERTICES] = {0};

    // Perform BFS starting from each unvisited vertex

    printf("BFS Traversal Order:\n");

    for (i = 0; i < numVertices; i++) {

        if (!visited[i]) {

            bfs(i, visited, adjacencyMatrix, numVertices);

        }

    }

    return 0;

}

Output

Enter the number of vertices (max 10): 5

Enter the adjacency matrix (1 for connected, 0 for not connected):

0 1 1 1 0

1 0 1 0 0

1 1 0 0 1

1 0 0 0 0

0 0 1 0 0

BFS Traversal Order:

V0 V1 V2 V3 V4 

Example: University Question

BFS: AEDBC