# 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) 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

#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