Program Explanation

The Breadth-First Search (BFS) algorithm is a traversing algorithm for graphs or trees.
It explores the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

In this implementation, we use a queue data structure to keep track of nodes to be explored.
The BFS function starts at a given node and explores all its neighbors before moving deeper.

Program Structure

1. Graph Representation: The graph is represented using an adjacency list.
2. Queue Implementation: A queue is implemented using an array to facilitate BFS.
3. BFS Function: This function takes the graph and the starting node to perform the BFS traversal.
4. Main Function: Initializes the graph and calls the BFS function.

Code Implementation

#include 
#include 

#define MAX 100

// Structure to represent a node in the adjacency list
struct Node {
    int vertex;
    struct Node* next;
};

// Structure to represent a queue
struct Queue {
    int items[MAX];
    int front;
    int rear;
};

// Function to create a new adjacency list node
struct Node* createNode(int vertex) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = vertex;
    newNode->next = NULL;
    return newNode;
}

// Function to initialize a queue
void initQueue(struct Queue* q) {
    q->front = -1;
    q->rear = -1;
}

// Function to check if the queue is empty
int isEmpty(struct Queue* q) {
    return q->rear == -1;
}

// Function to enqueue an item
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX - 1) {
        printf("Queue is full!\n");
    } else {
        if (q->front == -1) q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// Function to dequeue an item
int dequeue(struct Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        return item;
    }
}

// Function to perform BFS traversal
void bfs(struct Node* adjList[], int start, int visited[]) {
    struct Queue q;
    initQueue(&q);

    visited[start] = 1;
    enqueue(&q, start);

    printf("BFS Traversal: ");
    while (!isEmpty(&q)) {
        int current = dequeue(&q);
        printf("%d ", current);

        struct Node* temp = adjList[current];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!visited[adjVertex]) {
                visited[adjVertex] = 1;
                enqueue(&q, adjVertex);
            }
            temp = temp->next;
        }
    }
}

// Function to add an edge to the graph
void addEdge(struct Node* adjList[], int src, int dest) {
    struct Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;
}

// Main function
int main() {
    int vertices, edges, src, dest;
    struct Node* adjList[MAX];
    int visited[MAX] = {0};

    printf("Enter number of vertices: ");
    scanf("%d", &vertices);
    printf("Enter number of edges: ");
    scanf("%d", &edges);

    // Initialize adjacency list
    for (int i = 0; i < vertices; i++) {
        adjList[i] = NULL;
    }

    printf("Enter edges (src dest):\n");
    for (int i = 0; i < edges; i++) {
        scanf("%d %d", &src, &dest);
        addEdge(adjList, src, dest);
        addEdge(adjList, dest, src); // For undirected graph
    }

    printf("Starting BFS from vertex 0:\n");
    bfs(adjList, 0, visited);

    return 0;
}

How to Compile and Run

To compile and run this program, follow these steps:

1. 1. Save the code in a file named bfs.c.
   2. Open a terminal and navigate to the directory where bfs.c is located.
   3. Compile the program using the following command:

gcc bfs.c -o bfs

1. 1. Run the program:

./bfs