• »
Breadth First Search C Program

Explanation

Here is a c program demonstrating breadth first search using Queue datastructure and it is written for clarity than performance.

Create a queue structure with variable front and rear

/* Queue structure */
struct queue {
  int items[1024];
  int front, rear;
} q;

Check if the queue is empty, by checking if rear and front points to the same index

/* Check if Queue is empty */
int isEmpty() {
  int i = (q.rear == q.front)?1:0;
  return i;
}

Enqueue adds an element to the end of the queue.

/* Enqueue an item */
void enqueue(int item, int length){
  if(q.rear == (length - 1))
    q.rear = 0;
  else 
    q.rear++;
		
  q.items[q.rear] = item;    
}

Dequeue removes an element from the front of the queue.

/* Dequeue an item */
int dequeue(int length){
  if(isEmpty()){
    return -1;
  }
  if(q.front == (length - 1)){
    q.front = 0;
  } else 
    q.front++;
		
  return q.items[q.front];
}

Here is the breadth first search snippet.

int bfs(int graph[][5], int seed, int length) {
  //color = 0 -- not visited
  //color = 1 -- visited
  int color[length], count = 0, i = 0, j = 0;

  if(seed > length) return -1;

  for(i = 0; i < length; ++i){
    color[i] = 0;
  }

  //mark seed node as visited
  color[seed] = 1;
  q.front = q.rear = length - 1;

  //add seed to queue -- to check all its neighbours
  enqueue(seed, length);

  /* loop until queue has no nodes to check for neighbours */
  while(!isEmpty()) {
  i = dequeue(length);

  if( i == -1)
      continue;

  //check neighbours of node
    for(j = 0; j < length; ++j) {
    if(graph[i][j] > 0) {

        //if already not visited -- visit them
      if( color[j] == 0) {
          color[j] = 1;
          enqueue(j, length);
        }
      }
  }
    color[i] = 2;
}

  for(i = 0; i < length; ++i) {
    if(color[i] >= 1)
      count++;
    else
      printf("Not visited node: %d\n", i);
  }

  return count;
}


Source code

New York based Software Engineer and a node.js fan. Apart from writing tons of code for living and passion, I am interested in Astrophysics, Cooking and Philosophy.

You can reach out to me at arjun@rdaemon.com

powered by Disqus