# 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

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()
{
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

### 1 thought on “Breadth First Search or BFS | C Programming | DSA | Factsprime”

1. What’s up it’s me, I am аlso visiting thiѕ website regularly, tһiѕ web ⲣage is genuinely fastidious
аnd thｅ viewers are actually sharing good thoughts.