Breadth-First Search (BFS) Traversal in Graph: C Program Example

C Program to implement Graph Structure: Exercise-5 with Solution

Write a C program to perform BFS (Breadth-First Search) traversal on a graph. Print the order of visited vertices.

From Wikipedia,

Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored.

For example, in a chess endgame, a chess engine may build the game tree from the current position by applying all possible moves and use breadth-first search to find a win position for White. Implicit trees (such as game trees or other problem-solving trees) may be of infinite size; breadth-first search is guaranteed to find a solution node[1] if one exists.

Animated example of a breadth-first search. Black: explored, grey: queued to be explored later on

Source: Wikipedia

Sample Solution:

C Code:

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

#define MAX_VERTICES 100

// Function to add an edge to the graph
void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int start, int end) {
    graph[start][end] = 1;
    graph[end][start] = 1; // For undirected graph
}

// Function to perform BFS traversal
void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int startVertex) {
    int visited[MAX_VERTICES] = {0}; // Initialize all vertices as not visited
    int queue[MAX_VERTICES];
    int front = -1, rear = -1;

    // Mark the startVertex as visited and enqueue it
    visited[startVertex] = 1;
    queue[++rear] = startVertex;

    printf("BFS Traversal Order: ");

    while (front != rear) {
        int currentVertex = queue[++front];
        printf("%d ", currentVertex);

        for (int i = 0; i < vertices; i++) {
            if (graph[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = 1;
                queue[++rear] = i;
            }
        }
    }

    printf("\n");
}

int main() {
    int vertices, edges;

    // Input the number of vertices
    printf("Input the number of vertices: ");
    scanf("%d", &vertices);

    if (vertices <= 0 || vertices > MAX_VERTICES) {
        printf("Invalid number of vertices. Exiting...\n");
        return 1;
    }

    int graph[MAX_VERTICES][MAX_VERTICES] = {0}; // Initialize the adjacency matrix with zeros

    // Input the number of edges
    printf("Input the number of edges: ");
    scanf("%d", &edges);

    if (edges < 0 || edges > vertices * (vertices - 1) / 2) {
        printf("Invalid number of edges. Exiting...\n");
        return 1;
    }

    // Input edges and construct the adjacency matrix
    for (int i = 0; i < edges; i++) {
        int start, end;
        printf("Input edge %d (start end): ", i + 1);
        scanf("%d %d", &start, &end);

        // Validate input vertices
        if (start < 0 || start >= vertices || end < 0 || end >= vertices) {
            printf("Invalid vertices. Try again.\n");
            i--;
            continue;
        }

        addEdge(graph, start, end);
    }

    // Input the starting vertex for BFS traversal
    int startVertex;
    printf("Input the starting vertex for BFS traversal: ");
    scanf("%d", &startVertex);

    // Perform BFS traversal
    BFS(graph, vertices, startVertex);

    return 0;
}

Output:

Input the number of vertices: 5
Input the number of edges: 6
Input edge 1 (start end): 0 1
Input edge 2 (start end): 1 2
Input edge 3 (start end): 2 3
Input edge 4 (start end): 3 4
Input edge 5 (start end): 4 0
Input edge 6 (start end): 2 4
Input the starting vertex for BFS traversal: 0
BFS Traversal Order: 0 1 4 2 3

Explanation:

In the exercise above,

• Header Files:
• #include <stdio.h>: Provides input and output functions.
• #include <stdlib.h>: Provides memory allocation and other utility functions.
• Macro Definition:
• #define MAX_VERTICES 100: Defines the maximum number of vertices in the graph.
• Function to Add an Edge:
• void addEdge(int graph[MAX_VERTICES][MAX_VERTICES], int start, int end): Adds an edge between two vertices in the adjacency matrix, indicating a connection in the graph.
• Function to Perform BFS Traversal:
• void BFS(int graph[MAX_VERTICES][MAX_VERTICES], int vertices, int startVertex): Performs BFS traversal on the graph starting from the specified vertex.
• Uses a queue to keep track of visited vertices and their neighbors.
• Prints the order of visited vertices.
• Main Function:
• Reads the number of vertices (vertices) and edges (edges) from the user.
• Constructs an adjacency matrix (graph) to represent the graph.
• Takes input for edges, validates input vertices, and adds edges to the graph.
• Takes input for the starting vertex for BFS traversal (startVertex).
• Calls the BFS function to perform BFS traversal and prints the order of visited vertices.

Flowchart:

C Programming Code Editor:

Previous: Program for DFS traversal in Graph.
Next: Cycle detection in Graph: C Program implementation.