Graph Traversal - BFS

Write a C program for finding the Breadth First Search of a graph.

// C program for finding the Breadth First Search of a graph 

#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,i;

    // 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 ( i = 0; i < vertices; i++) {

            if (graph[currentVertex][i] == 1 && !visited[i]) {

                visited[i] = 1;

                queue[++rear] = i;

            }

        }

    }

    printf("\n");

}

// Function to print the adjacency matrix

void printAdjacencyMatrix(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {

    int i, j;

    printf("Adjacency Matrix:\n");

    for (i = 0; i < vertices; i++) {

        for (j = 0; j < vertices; j++) {

            printf("%d ", graph[i][j]);

        }

        printf("\n");

    }

}

int main() {

    int vertices, edges,i;

    printf("\n****Breadth-First Search (BFS) traversal****\n");

    printf("-----------------------------------------------\n");

    // 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 (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);

    }

    // Print the adjacency matrix

    printAdjacencyMatrix(graph, vertices);

    // Input the starting vertex for BFS traversal

    int startVertex;

    printf("Input the starting vertex for BFS traversal: ");

    scanf("%d", &startVertex);

    if (startVertex < 0 || startVertex >= vertices) {

        printf("Invalid starting vertex. Exiting...\n");

        return 1;

    }

    // Perform BFS traversal

    BFS(graph, vertices, startVertex);

    return 0;

}

Input/Output:

****Breadth-First Search (BFS) traversal****

-----------------------------------------------

Input the number of vertices: 7

Input the number of edges: 11

Input edge 1 (start end): 0 1

Input edge 2 (start end): 0 3

Input edge 3 (start end): 0 4

Input edge 4 (start end): 3 4

Input edge 5 (start end): 1 4

Input edge 6 (start end): 1 2

Input edge 7 (start end): 4 2

Input edge 8 (start end): 4 5

Input edge 9 (start end): 2 5

Input edge 10 (start end): 2 6

Input edge 11 (start end): 5 6

Adjacency Matrix:

0 1 0 1 1 0 0

1 0 1 0 1 0 0

0 1 0 0 1 1 1

1 0 0 0 1 0 0

1 1 1 1 0 1 0

0 0 1 0 1 0 1

0 0 1 0 0 1 0

Input the starting vertex for BFS traversal: 0

BFS Traversal Order:  0 -->  1 -->  3 -->  4 -->  2 -->  5 -->  6 -->

--------------------------------

Process exited after 49.83 seconds with return value 0

Press any key to continue . . .