BFS Program in C - Naukri Code 360

Introduction

Breadth-First Search (BFS) is a pivotal algorithm in the field of computer science, particularly for those diving into the depths of data structures & algorithms. This traversal technique explores a graph or tree layer by layer, ensuring no node is overlooked.

Its practicality shines in numerous applications, from AI to network broadcasting, making its understanding essential for coding students.

How does BFS work?

Breadth-First Search (BFS) operates on a simple yet effective principle: it starts at a selected node (often referred to as the 'source node') and explores all its neighbors at the current depth before moving on to nodes at the next level of depth.

Key Concepts of BFS

Queue Data Structure

BFS uses a queue to keep track of the nodes to be explored next.

Visited Array

To avoid revisiting nodes, BFS maintains a list or array of visited nodes.

Level-wise Exploration

Nodes are visited level by level, ensuring complete traversal.

Process Breakdown

Initialization: The source node is marked as visited & enqueued.
Traversal: While the queue is not empty, the node at the front of the queue is dequeued & its unvisited neighbors are marked as visited & enqueued.
Completion: The process continues until the queue is empty, indicating all reachable nodes have been visited.

BFS Program in C using Adjacency List

When implementing BFS in C, one efficient way to represent a graph is through an adjacency list. This method uses an array of lists to represent the connections between nodes. Here's a step-by-step guide on how to create a BFS program using an adjacency list:

1. Structure Definition

First, define a structure for the graph and the nodes in the list:

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

typedef struct node {
    int vertex;
    struct node* next;
} Node;

typedef struct graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

2. Node Creation

Create a function to create a new node:

Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

3. Graph Initialization

Initialize the graph with the number of vertices and allocate memory:

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(int));
    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

4. Adding Edges

Add edges to the graph:

void addEdge(Graph* graph, int src, int dest) {
    // Add edge from src to dest
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    // Add edge from dest to src for undirected graph
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

5. BFS Implementation

Implement the BFS algorithm using a queue:

void bfs(Graph* graph, int startVertex) {
    Node* queue = createQueue();

    graph->visited[startVertex] = 1;
    enqueue(queue, startVertex);
    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("Visited %d\n", currentVertex);

        Node* temp = graph->adjLists[currentVertex];

        while (temp) {
            int adjVertex = temp->vertex;

            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
}

BFS Program in C using Adjacency Matrix

Another common way to implement BFS in C is by using an adjacency matrix. This approach is particularly useful for dense graphs where the matrix representation might be more space-efficient than a list.

1. Structure Definition

Start by defining the graph structure with a matrix:

#include <stdio.h>
#include <stdlib.h>
typedef struct graph {
    int numVertices;
    int** adjMatrix;
    int* visited;
} Graph;

2. Graph Initialization

Initialize the graph with the number of vertices:

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjMatrix = malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        graph->adjMatrix[i] = malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++)
            graph->adjMatrix[i][j] = 0;
    }

    graph->visited = malloc(vertices * sizeof(int));
    for (int i = 0; i < vertices; i++)
        graph->visited[i] = 0;
  return graph;
}

3. Adding Edges

Function to add edges to the graph:

void addEdge(Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;
    graph->adjMatrix[dest][src] = 1; // For undirected graph
}

4. BFS Implementation

Implement BFS for the adjacency matrix:

void bfs(Graph* graph, int startVertex) {
    int queue[1000], front = -1, rear = -1;

    graph->visited[startVertex] = 1;
    queue[++rear] = startVertex;

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

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

BFS Program in C using Queue

In this section, we'll focus on implementing the Breadth-First Search (BFS) algorithm in C using a queue, a crucial data structure for managing the nodes during traversal.

1. Queue Implementation

First, we need to implement a queue that will be used in the BFS algorithm:

#include <stdio.h>
#include <stdlib.h>
typedef struct queue {
    int items[1000];
    int front;
    int rear;
} Queue;
Queue* createQueue() {
    Queue* q = malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}
int isEmpty(Queue* q) {
    return q->rear == -1;
}

void enqueue(Queue* q, int value) {
    if (q->rear == 999)
        printf("\nQueue is Full!!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

int dequeue(Queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

2. Graph Definition & Initialization

Define the graph structure & initialize it:

typedef struct graph {
    int numVertices;
    int** adjMatrix;
    int* visited;
} Graph;

Graph* createGraph(int vertices) {
    // [Graph Initialization Code from Previous Section]
}

3. BFS Implementation with Queue

Now, implement BFS using the queue:

void bfs(Graph* graph, int startVertex) {
    Queue* q = createQueue();
    graph->visited[startVertex] = 1;
    enqueue(q, startVertex);
    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("Visited %d\n", currentVertex);
        for (int j = 0; j < graph->numVertices; j++) {
            if (graph->adjMatrix[currentVertex][j] && !graph->visited[j]) {
                graph->visited[j] = 1;
                enqueue(q, j);
            }
        }
    }
}

Frequently Asked Questions

What makes BFS different from DFS in terms of graph traversal?

BFS (Breadth-First Search) explores a graph level by level, ensuring a comprehensive visit to each node's neighbors before diving deeper. In contrast, DFS (Depth-First Search) delves deep into one path of the graph before backtracking. This fundamental difference makes BFS suitable for shortest path finding, while DFS is often used for connectivity checking.

How does BFS handle cycles in a graph?

BFS can efficiently handle cycles in a graph by keeping track of visited nodes. When a node is visited, it's marked as such, preventing the algorithm from revisiting and entering an infinite loop. This mechanism is crucial for BFS's application in real-world problems like network routing.

Can BFS be used for weighted graphs?

While BFS is primarily designed for unweighted graphs, it can be adapted for weighted graphs in specific scenarios, especially when weights are uniform or irrelevant to the task at hand. However, for general pathfinding in weighted graphs, algorithms like Dijkstra's or A* are more appropriate due to their ability to factor in edge weights.

Conclusion

Breadth-First Search (BFS) is a fundamental algorithm in computer science, essential for students delving into graph theory and its applications. Through its implementation in C using different data structures like adjacency lists, matrices, and queues, we've explored its versatility and practical applications. This comprehensive look at BFS, equipped with code examples and explanations, aims to deepen understanding and inspire further exploration into this vital algorithm. Remember, the real power of BFS lies not just in the code, but in the logical thinking and problem-solving skills it fosters.

You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.