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.

c program for bfs using adjacency matrix

(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");
}



Related Contents to follow