# c program for bfs using adjacency matrix

write c program for bfs using adjacency matrix. For example the breadth first search of below graph from 0th vertex would be 0 1 2 6 3 4. We have already discuss BFS in detail in post http://wikistack.com/breadth-first-search-of-graph/ . This post is a step by step tutorial about BFS algorithm using c++ program.

Here we are implementing BFS using simple C program.

1 2 3 4 5 |
(1) push dfs starting node in the queue, mark it visited (2) while queue is not empty (3) get first node from the queue say it v (4) check all adjacent nodes from v (5) push adjacent nodes in queue and mark it visited |

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <stdio.h> #include <string.h> #define N 7 // visited array int visited[N]; // graph as adjacency matrix //0 1 2 3 4 5 6 int graph[N][N] = { { 0, 1, 1, 0, 0, 0, 0 }, //0 { 0, 0, 0, 0, 0, 0, 1 }, //1 { 0, 0, 0, 1, 0, 0, 1 }, //2 { 0, 0, 0, 0, 1, 0, 0 }, //3 { 0, 0, 0, 0, 0, 0, 1 }, //4 { 6, 0, 0, 1, 0, 0, 0 }, //5 { 0, 0, 0, 0, 0, 0, 0 }, //6 }; // queue implementation int front = 0; int rear = 0; int q[N] = { 0 }; void bfs(int v); int main() { // make all vertex unvisited memset(visited, 0, sizeof(visited)); // run bfs from 0th vertex bfs(0); return 0; } void bfs(int v) { // make vertex v visited visited[v] = 1; // enqueue vertex v q[rear] = v; // insert at rear rear++; // increment rear while (rear != front) // condition for empty queue { // dequeue int u = q[front]; printf("%d ", u); front++; // check adjacent nodes from u int i = 0; for (i = 0; i < N; i++) { // if there is adjacent vertex enqueue it if (!visited[i] && graph[u][i]) { q[rear] = i; rear++; visited[i] = 1; } } } printf("\n"); } |

what is the output of this program?

output would be 0 1 2 6 3 4