Breadth First Search - BFS Algorithm with Practical Examples

• Breadth First Search
• BFS Algorithm
• Working Principle of BFS
• Implementation of BFS in C and C++
• Time Complexity of BFS
• Space Complexity of BFS
• Applications of BFS
• Run C Programming Online Compiler

Imagine a wildfire igniting in a vast, densely wooded forest. The fire starts at one point and spreads to adjacent areas. Fire moves to new areas directly adjacent to those already burning, creating a wave that moves outward from the origin. This spreading pattern mirrors the characteristics of the BFS algorithm, moving uniformly to all directly adjacent areas in successive waves.

Breadth-First Search (BFS) is commonly used in various tasks such as routing in networks, navigating social networks, crawling web pages, guiding GPS navigation, solving puzzles, and managing memory in programming through garbage collection.

¶Breadth First Search

Breadth First Search (BFS) is a fundamental traversing algorithm in graph theory. It begins at a specific node and explores all neighboring nodes at the current level before moving on to nodes at the next level. Numerous graph algorithms heavily rely on BFS. For instance, searching for the shortest path from one node to another in a graph often utilizes BFS. This algorithm systematically explores neighboring nodes, making it particularly efficient for finding optimal paths.

¶BFS Algorithm

Breadth-First Search (BFS) begins at a chosen vertex and explores neighboring vertices iteratively in a level-by-level manner. Here’s a basic outline of the BFS algorithm:

1. Choose a starting vertex and mark it as visited.
2. Enqueue the starting vertex into a queue data structure.
3. While the queue is not empty,
   • Dequeue a vertex from the front of the queue.
   • Visit the dequeued vertex and explore its adjacent vertices.
   • For each unvisited adjacent vertex, mark it as visited and enqueue it into the queue.
4. Repeat step 3 until all reachable vertices are visited or the queue becomes empty.
5. If all reachable vertices are visited, terminate the algorithm. Otherwise, continue exploring vertices by dequeuing from the queue.

¶Working Principle of BFS

Let’s see working principle of BFS for the following graph,

1. Initialization:

   • Start at the node 1.
   • Create a queue to help manage the nodes to be explored and initialize it with the start node, in this case, queue = [1].
   • Mark node 1 as visited to avoid revisiting it visited = {1}.

2. Exploration:

   • Dequeue an element from the front of the queue. Here, we start with node 1. current_node = 1.
   • Examine each adjacent node of node 1. According to the graph, these are nodes 2 and 3.

3. Checking and Enqueuing Neighbors of Node 1:

   • For each adjacent node:
     • If it has not been visited, mark it as visited and enqueue it.
     • Process node 2: Mark as visited (visited = {1, 2}) and enqueue (queue = [2]).
     • Process node 3: Mark as visited (visited = {1, 2, 3}) and enqueue (queue = [2, 3]).

4. Continuing with Node 2:

   • Dequeue node 2. current_node = 2.
   • Examine its neighbors (nodes 6 and 4).
     • Node 6: Mark as visited (visited = {1, 2, 3, 6}) and enqueue (queue = [3, 6]).
     • Node 4: Mark as visited (visited = {1, 2, 3, 6, 4}) and enqueue (queue = [3, 6, 4]).

5. Continuing with Node 3:

   • Dequeue node 3. current_node = 3.
   • Examine its neighbors (nodes 4 and 5).
     • Node 4 is already visited, so ignore.
     • Node 5: Mark as visited (visited = {1, 2, 3, 6, 4, 5}) and enqueue (queue = [6, 4, 5]).

6. Finishing Up:

   • Continue the process until the queue is empty, dequeuing nodes 6, 4, and 5 sequentially, each time checking their neighbors. Since all neighbors will have been already visited by the time we process these nodes, no new nodes are added to the queue.
   • Once the queue is empty, the BFS traversal is complete.

The final order of traversal in BFS starting from node 1 in this graph will be: 1, 2, 3, 6, 4, 5. This order reflects how BFS explores all neighbors at the current depth before moving to nodes at the next depth level.

¶Implementation of BFS in C and C++

Here is the C implementation of BFS

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTICES 100

int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];
int queue[MAX_VERTICES];
int front = -1, rear = -1;

void enqueue(int vertex) { queue[++rear] = vertex; }
int dequeue() { return queue[++front]; }
bool isEmpty() { return front == rear; }

void addEdge(int u, int v) {
    graph[u][v] = 1;
    graph[v][u] = 1; // Since the graph is undirected
}

void BFS(int startVertex, int numVertices) {
    visited[startVertex] = true;
    enqueue(startVertex);

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

        for (int i = 1; i <= numVertices; i++) {
            if (graph[currentVertex][i] && !visited[i]) {
                visited[i] = true;
                enqueue(i);
            }
        }
    }
}

int main() {
    int numVertices = 6;
    // Initialize graph (adjacency matrix) and visited array
    for (int i = 0; i < MAX_VERTICES; i++) {
        for (int j = 0; j < MAX_VERTICES; j++) {
            graph[i][j] = 0;
        }
        visited[i] = false;
    }

    // Adding edges as per your graph
    addEdge(1, 2);
    addEdge(1, 3);
    addEdge(2, 6);
    addEdge(2, 4);
    addEdge(3, 4);
    addEdge(3, 5);

    printf("BFS starting from vertex 1:\n");
    BFS(1, numVertices);

    return 0;
}

Here is the C++ implementation of BFS

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

using namespace std;

// Function to add an edge to the graph (undirected graph)
void addEdge(vector<int> adj[], int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u); // Since the graph is undirected
}

// Function to perform BFS on the graph
void BFS(vector<int> adj[], int startVertex, int numVertices) {
    vector<bool> visited(numVertices + 1, false); // +1 for 1-based index
    queue<int> queue;

    // Start from the given starting vertex
    visited[startVertex] = true;
    queue.push(startVertex);

    while (!queue.empty()) {
        int vertex = queue.front();
        queue.pop();
        cout << vertex << " ";

        // Visit all the adjacent vertices
        for (int adjVertex : adj[vertex]) {
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                queue.push(adjVertex);
            }
        }
    }
    cout << endl;
}

int main() {
    int numVertices = 6; // 6 vertices labeled from 1 to 6
    vector<int> adj[numVertices + 1]; // +1 for 1-based index

    // Adding edges as per your graph
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 6);
    addEdge(adj, 2, 4);
    addEdge(adj, 3, 4);
    addEdge(adj, 3, 5);

    cout << "Breadth First Search starting from vertex 1:" << endl;
    BFS(adj, 1, numVertices);

    return 0;
}

¶Time Complexity of BFS

The time complexity of BFS algorithm is O(V + E), where V is the number of nodes and E is the number of edges.

¶Space Complexity of BFS

The space complexity of BFS is O(∣V∣), where ∣V∣ represents the number of vertices in the graph.

¶Applications of BFS

Here are a few real-life applications of BFS:

1. Routing in Networks: BFS is used to find the shortest path in network routing to ensure data packets are sent via the shortest possible routes, minimizing latency and maximizing efficiency.

2. Navigating Social Networks: In social networks, BFS helps to explore user connections level by level, allowing features like finding friends of friends or suggesting new friends based on shortest connection paths.

3. Crawling Web Pages: Search engines use BFS to systematically visit web pages by starting at a source page and visiting all linked pages before moving to links that are two hops away, ensuring a thorough and orderly exploration of the web.

4. Guiding GPS Navigation: BFS is applied in GPS systems to compute the shortest path from one location to another by exploring all possible routes systematically, starting from the nearest and expanding outward.

5. Solving Puzzles: BFS is effective for solving puzzles like the sliding tile puzzle or the Rubik’s Cube by exploring all possible states from the initial configuration to find the solution that requires the fewest moves.

6. Managing Memory in Programming through Garbage Collection: In garbage collection, BFS can be used to identify all reachable objects in memory so that unreachable objects can be cleared, ensuring efficient memory use and preventing memory leaks.

Each application utilizes the structured, layer-by-layer exploration characteristic of BFS to achieve efficient and optimal solutions in their respective fields.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online