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() { // 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
What’s up it’s me, I am аlso visiting thiѕ website regularly, tһiѕ web ⲣage is genuinely fastidious
аnd the viewers are actually sharing good thoughts.