Breadth First Search or BFS | C Programming | DSA | Factsprime

Write a Modular C Programming code to implement Breadth First Search or BFS traversal using Matrix in a given Graph DSA

Example: 

In the following graph, we start traversal from vertex 2.

When we come to vertex 0, we look for all adjacent vertices of it. 

• 2 is also an adjacent vertex of 0. 
• If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process.

There can be multiple BFS traversals for a graph. Different BFS traversals for the above graph :
2, 3, 0, 1
2, 0, 3, 1

Refer : C Programming HackerRank all solutions for Loops | Arrays | strings | Data Structures | Linked lists | Stacks | Queues | Binary Trees

CODE:

#include<stdio.h>

#define V 9
void BFS(int adj_matrix[V][V], int start) {
    int queue[V], front = -1, rear = -1;
    int visited[V] = {0}; // Mark all vertices as not visited

    // Enqueue starting vertex and mark it as visited
    queue[++rear] = start;
    visited[start] = 1;

    while (front != rear) { // While the queue is not empty
        // Dequeue a vertex from the queue
        int curr = queue[++front];
        printf("%d ", curr);

        // Check all adjacent vertices of the dequeued vertex
        for (int i = 0; i < V; i++) {
            if (adj_matrix[curr][i] == 1 && !visited[i]) {
                // Enqueue the adjacent vertex if it is not visited
                queue[++rear] = i;
                visited[i] = 1;
            }
        }
    }
}
int main()
{
    // Example adjacency matrix
    int graph[V][V] = {
        {0, 1, 0, 0, 1, 1, 0, 0, 0},
        {1, 0, 1, 0, 0, 0, 1, 0, 0},
        {0, 1, 0, 1, 0, 0, 0, 1, 0},
        {0, 0, 1, 0, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 0, 1, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0, 0, 1, 0},
        {0, 0, 1, 0, 0, 0, 1, 0, 1},
        {0, 0, 0, 1, 1, 0, 0, 1, 0}
    };

    int visited[V] = { 0 };  // Initialize all vertices as unvisited


    printf("\n\nBFS Traversal: ");
    BFS(graph, 0); // Start BFS traversal from vertex 0
    printf("\n");

    return 0;
}

OUTPUT

BFS Traversal: 0 1 4 5 2 6 8 3 7

Process returned 0 (0x0)   execution time : 0.036 s
Press any key to continue.

Please find some more codes of Loops, Condition Statements, 1D Arrays, 2D Arrays, Strings, Pointers, Data Structures, Files, Linked lists, Stacks, Queues, Binary Trees, MISC, Solved model question papers & Hacker Rank all solutions on the below page:

Top 100+ C Programming codes – KLE Technological University