C Program To Implement Breath First Search

Breath First Search is a graph searching algorithm which begins at the start vertex and explores all adjacent nodes.  Then for each adjacent vertex, it finds their adjacent nodes and so on.  And this process continues until all possible vertices are explored.

Breath First Search Example:
Step 1:  Enqueue the starting vertex V1.

                   +-------------------- V1 -----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+   +-------------------- V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------  V6  ---------------------+

              +------------------+
Queue:   |  V1 |      |       |
              +------------------+

Step 2:  Find the unvisited adjacent vertices to the vertex V1.  Vertices V2 and V3 are adjacent to vertex V1.  Dequeue V1 and insert its adjacent vertices into the queue.

                   +----------------------- V1 -------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+   +-------------------- V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------  V6  ---------------------+

              +------------------+
Queue:   |  V2 | V3  |       |
              +------------------+

Visited Node:  V1

Step 3:  Find the unvisited vertices adjacent to V2.  V4 and V6 are the unvisited adjacent vertices.  Dequeue V2, enqueue V4 and V6

                   +-------------------- V1 ----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+  +----------------------V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +-------------------  V6  ----------------------+

              +-------------------------------+
Queue:   |  V3 | V4  | V6  |      |      |
              +-------------------------------+

Visited Nodes:  V1, V2

Step 4:  Find the unvisited vertices adjacent to V3.  V5 is the unvisited vertex adjacent to V3.  Enqueue V5 and dequeue V3.

                   +-------------------- V1 ----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+  +----------------------V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------- V6  ---------------------+

             +-------------------------------+
Queue:  |  V4 | V6  | V5  |      |      |
             +-------------------------------+

Visited Nodes:  V1, V2, V3

Step 5:  There is no unvisited vertex adjacent to V4.  So, dequeue V4 and mark it as visited.

                   +-------------------- V1 ----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+  +----------------------V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------- V6  ---------------------+

              +-------------------------------+
Queue:   |  V6 | V5  |      |      |       |
              +-------------------------------+

Visited Nodes:  V1, V2, V3, V4

Step 6:  There is no unvisited vertex adjacent to V6.  So, dequeue V6 and mark it as visited.

                   +-------------------- V1 ----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+  +----------------------V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------- V6  ---------------------+

              +-------------------------------+
Queue:   |  V5 |       |      |      |      |
              +-------------------------------+

Visited Nodes:  V1, V2, V3, V4, V6

Step 7:  There is no unvisited vertex adjacent to V4.  So, dequeue V5 and mark it as visited.

                   +-------------------- V1 ----------------------+
                   |                                                         |
                   |                                                         |
                  V2 -------------------+  +----------------------V3
                   |                         |  |                           |
                   |                         |  |                           |
                   V4                       |  |                          V5
                   |                         |  |                           |
                   |                         |  |                           |
                   +--------------------- V6  ---------------------+

              +--------------------------------+
Queue:   |       |       |      |      |      |
              +--------------------------------+

Visited Nodes:  V1, V2, V3, V4, V6, V5

So, the input graph is visited in the below order
V1, V2, V3, V4, V6, V5

See Also:
C Program To Implement Dijkstra's Algorithm
C Program To Find Minimum Spanning Tree Using Prim's Algorithm
C Program To Find Minimum Spanning Tree Using Kruskal's Algorithm
C Program To Implement Breath First Search
C Program To Implement Depth First Search

Example Program To Implement Breath First Search(in C):

---

  #include <stdio.h>
  #include <stdlib.h>

  #define VERTEXCOUNT 6
  #define VISITED 1

  struct node {
        int data;
        struct node *next;
  };

  int visitVertex[VERTEXCOUNT], queue[VERTEXCOUNT];
  int front = -1, rear = -1;

  struct node * createNode(int data) {
        struct node *newnode;
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->data = data;
        newnode->next = NULL;
        return newnode;
  }

  /* enqueue the data in to the queue */
  void enqueue(int data) {
        if (rear >= VERTEXCOUNT -1) {
                printf("Queue overflow!!\n");
                exit(0);
        }
        rear++;
        queue[rear] = data;
        if (front == -1)
                front++;
        return;
  }

  /* dequeue operation */

  void dequeue() {

        if (front == -1) {

                printf("Queue Underflow!!\n");

                exit(0);

        }

        queue[front] = 0;

        if (front == rear)

                front = rear = -1;

        else

                front++;

        return;

  }

  void breathFirstSearch(int index, struct node *vertex[]) {

        struct node *temp;

        visitVertex[index - 1] = VISITED;

        enqueue(index);

        printf("VV(Visited Vertex): %d\n", index);

        while (front != -1) {

                /* dequeue front elment from the queue */

                dequeue();

                temp = vertex[index - 1];

                while (temp) {

                        /* adjacent unvisited vertices are enqueued */

                        if (visitVertex[temp->data - 1] != VISITED) {

                                enqueue(temp->data);

                                visitVertex[temp->data - 1] = VISITED;

                                printf("VV(Visited Vertex): %d\n", temp->data);

                        }

                        temp = temp->next;

                }

                index++;

        }

  }

  /* delete nodes in the given list */

  void deleteNodes(struct node *myNode) {

        struct node *temp;

        while (myNode != NULL) {

                temp = myNode;

                myNode = myNode->next;

                free(temp);

        }

  }

  int main() {

        struct node *vertex[VERTEXCOUNT], *newnode;

        int index = 0;

        /* construct adjacency list for the input graph */

        newnode = createNode(2);

        vertex[0] = newnode;

        newnode->next = createNode(3);

        newnode = createNode(1);

        vertex[1] = newnode;

        newnode->next = createNode(4);

        newnode->next->next = createNode(6);

        newnode = createNode(1);

        vertex[2] = newnode;

        newnode->next = createNode(5);

        newnode->next->next = createNode(6);

        newnode = createNode(2);

        vertex[3] = newnode;

        newnode->next = createNode(6);

        newnode = createNode(3);

        vertex[4] = newnode;

        newnode->next = createNode(6);

        newnode = createNode(2);

        vertex[5] = newnode;

        newnode->next = createNode(3);

        newnode->next->next = createNode(4);

        newnode->next->next->next = createNode(5);

        breathFirstSearch(1, vertex);

        /* delete all nodes in the graph */

        while (index < VERTEXCOUNT) {

                deleteNodes(vertex[index]);

                index++;

        }

        return 0;

  }

  Output: (C Program To Implement Breath First Search)

  jp@jp-VirtualBox:~/$ ./a.out
  VV(Visited Vertex): 1
  VV(Visited Vertex): 2
  VV(Visited Vertex): 3
  VV(Visited Vertex): 4
  VV(Visited Vertex): 6
  VV(Visited Vertex): 5