Breadth-First Graph Traversal using Queue – a C Implementation

There’re two common ways of visiting all nodes of a graph, depth-first search and breadth-first search. These two graph traversal approaches relate to two popular data structures, stack and queue respectively. (One can also do it in a recursive manner. It’s more intuitive but less efficient.)

This post covers breadth-first search with a queue data structure. The algorithm expressed in pseudo code is as below,

BFS (Graph, root):
    create a queue Q
    enqueue root node to Q
    while Q is not empty:
        dequeue an itme v from Q
        mark the item v as visited
        for each node w that is directed from v:
            if w is not visited:
                enqueue w to Q

The first step of the implementation is to implement a queue. The queue implemented below has the basic functions like enqueue, dequeue, ifEmpty, etc.

1. A Queue Implementation

The header file queue.h, defines the data structures used in Queue and Graph.

#include <stdio.h>
#include <stdlib.h>
typedef struct Point {
   int h;
   int w;
} Point;
typedef struct GraphNode {
   struct Point pvalue;
   struct GraphNode* left;
   struct GraphNode* right;
} GraphNode;
typedef struct QueueElement {
   struct GraphNode value;
   struct QueueElement *next;
} QueueElement;
typedef struct Queue {
   struct QueueElement* head;
   struct QueueElement* tail;
} Queue;
void initQueue(struct Queue *q);
void enqueue(struct Queue *q, struct GraphNode _value);
void dequeue(struct Queue *q);
struct GraphNode front(struct Queue *q);
int ifEmpty(struct Queue *q);

The source file queue.c,

/**
a C queue implementation using linked list
*/
#include "queue.h"
/*initialize the queue*/
void initQueue(struct Queue *q) {
   q->head = NULL;
   q->tail = NULL;
}
/*insert an element to the end of the queue*/
void enqueue(struct Queue *q, struct GraphNode _value) {
   //allocate a new QeueuElement for _value
   QueueElement *newElement;
   newElement = (QueueElement*) malloc(sizeof(QueueElement));
   newElement->value = _value;
   newElement->next = NULL;
   if (q->head == NULL) {
        //first element
       q->head = newElement;
       q->tail = newElement;
   } else {
        //put it to the tail
        q->tail->next = newElement;
        q->tail = newElement;
   }
}
/*delete the first element from the queue*/
void dequeue(struct Queue *q) {
   QueueElement *element;
   if (q->head == NULL) {
        //empty queue
        return;
   } else {
        element = q->head;
        q->head = q->head->next;
        free(element);
   }
}
/*get the front value of the queue, but don't delete it*/
struct GraphNode front(struct Queue *q) {
   return q->head->value;
}
/*check if the queue is empty*/
int ifEmpty(struct Queue *q) {
   return (q->head == NULL ? 1:0);
}

Note that the front() function above returns the first element of the queue and the dequeue() function deletes the first element from the queue. Some queue implementations has the dequeue() function does both return and delete. But I personally think separating them is more convenient as sometimes you just want to take a look at the queue but not delete anything from it.

The Queue above will take input element of GraphNode type, but you’re free to modify it to fit your needs.

2. The Breadth-First Graph Traversal

For simplicity, an example of visiting all nodes of a binary tree is given below. The tree structure is included in the comment of the source code file bfs.c,

#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
/* a simple graph (binary tree)
         (0,    3)   <– root node
          /     \
      (1, 2)    (1,4)
       /  \     /   \
   (2,1) (2,2) (2,3) (2,5)
*/
typedef struct Graph {
   struct GraphNode* root;
} Graph;
struct GraphNode initNode(int _h, int _w) {
   struct GraphNode node;
   node.pvalue.h = _h;
   node.pvalue.w = _w;
   node.left = NULL;
   node.right = NULL;
   return node;
}
int main() {
   struct Graph g;
   struct GraphNode currentNode;
   /*read in the graph from top to bottom*/
   g.root = (GraphNode*) malloc(sizeof(GraphNode));
   *g.root = initNode(0, 3);
   //level 2 nodes
   g.root->left = (GraphNode*) malloc(sizeof(GraphNode));
   *g.root->left = initNode(1, 2);
   g.root->right = (GraphNode*) malloc(sizeof(GraphNode));
   *g.root->right = initNode(1, 4);
   //level 3 nodes
   (*g.root->left).left = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->left).left = initNode(2, 1);
   (*g.root->left).right = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->left).right = initNode(2, 2);
   (*g.root->right).left = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->right).left = initNode(2, 3);
   (*g.root->right).right = (GraphNode*) malloc(sizeof(GraphNode));
   *(*g.root->right).right = initNode(2, 5);
   /*BFS traversal*/
   Queue q;
   initQueue(&q);
   enqueue(&q, *g.root);
   while (!ifEmpty(&q)) {
       currentNode = front(&q);
       //dequeue(&q); //you can either put dequeue here or at the end of while
        //mark as visited, here we simply print the graph node value out
       printf("(%d, %d)\n", currentNode.pvalue.h, currentNode.pvalue.w);
        //at most two children, left and right. As the binary tree is acyclic,
        // both nodes should not be visited yet, for cyclic graphs, 
        //one need additional methods to check if the nodes is visited or not before enqueue
       if (currentNode.left != NULL) {
           enqueue(&q, *currentNode.left);
       } 
       if (currentNode.right != NULL) {
           enqueue(&q, *currentNode.right);
        } 
        dequeue(&q);
   }
   return 0;
}

3. Output

To compile the code in Linux, type the following command,

gcc queue.c bfs.c -o bfs

Then run the binary bfs,

        ./bfs

The output we’ll get is,

(0, 3)

(1, 2)

(1, 4)

(2, 1)

(2, 2)

(2, 3)

(2, 5)

which corresponds to the expected nodes visiting order in breadth-first search, level 0 node, follows by level 1 nodes, and finally level 2 nodes.