BFS algorithm in C

Learn bfs algorithm in c with practical examples, diagrams, and best practices. Covers c, algorithm, binary-tree development techniques with visual explanations.
Tags:
Categories:

Implementing Breadth-First Search (BFS) in C

Hero image for BFS algorithm in C

Explore the fundamentals of the Breadth-First Search (BFS) algorithm, its applications, and a practical C implementation for traversing graphs and trees.

Breadth-First Search (BFS) is a fundamental algorithm for traversing or searching tree or graph data structures. It systematically explores all nodes at the current depth level before moving on to nodes at the next depth level. This article will delve into the core concepts of BFS, illustrate its working principle, and provide a robust C implementation.

BFS starts at a specified source node and explores all its immediate neighbors. Then, for each of those neighbors, it explores their unexplored neighbors, and so on. This process continues until all reachable nodes have been visited. The key characteristic of BFS is that it explores nodes layer by layer, ensuring that all nodes at depth 'd' are visited before any nodes at depth 'd+1'. This property makes BFS ideal for finding the shortest path in an unweighted graph.

flowchart TD
    A[Start Node] --> B(Add to Queue)
    B --> C{Queue not empty?}
    C -->|Yes| D(Dequeue Node 'u')
    D --> E(Mark 'u' as Visited)
    E --> F(Process 'u')
    F --> G{For each unvisited neighbor 'v' of 'u'}
    G -->|Yes| H(Mark 'v' as Visited)
    H --> I(Enqueue 'v')
    I --> G
    G -->|No| C
    C -->|No| J[End]

Flowchart illustrating the Breadth-First Search (BFS) algorithm process.

Core Components of BFS Implementation

To implement BFS, you typically need two main data structures:

  1. Queue: A queue is essential for maintaining the order of nodes to be visited. Nodes are added to the back (enqueue) and removed from the front (dequeue), ensuring the 'breadth-first' exploration.
  2. Visited Array/Set: To prevent infinite loops in graphs with cycles and to ensure each node is processed only once, a mechanism to track visited nodes is necessary. This is often an array of booleans or an integer array/set.

For representing the graph itself, an adjacency list (an array of linked lists) is commonly used, as it efficiently stores neighbors for each node.

C Implementation Example

Below is a C implementation of BFS for an undirected graph represented using an adjacency list. We'll use a simple array-based queue for demonstration purposes.

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

#define MAX_NODES 100

// Structure for a node in the adjacency list
struct Node {
    int data;
    struct Node* next;
};

// Structure for the graph
struct Graph {
    int numVertices;
    struct Node** adjLists;
    int* visited;
};

// Queue structure for BFS
struct Queue {
    int items[MAX_NODES];
    int front;
    int rear;
};

// Function to create a queue
struct Queue* createQueue() {
    struct Queue* q = malloc(sizeof(struct Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// Check if the queue is empty
int isEmpty(struct Queue* q) {
    if (q->rear == -1)
        return 1;
    else
        return 0;
}

// Add an element to the queue
void enqueue(struct Queue* q, int value) {
    if (q->rear == MAX_NODES - 1)
        printf("\nQueue is Full!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// Remove an element from the queue
int dequeue(struct 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;
}

// Create a node
struct Node* createNode(int v) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = v;
    newNode->next = NULL;
    return newNode;
}

// Create a graph
struct Graph* createGraph(int vertices) {
    struct Graph* graph = malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(struct Node*));
    graph->visited = malloc(vertices * sizeof(int));

    int i;
    for (i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0; // 0 for not visited, 1 for visited
    }
    return graph;
}

// Add edge
void addEdge(struct Graph* graph, int src, int dest) {
    // Add edge from src to dest
    struct 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;
}

// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
    struct Queue* q = createQueue();

    graph->visited[startVertex] = 1;
    enqueue(q, startVertex);

    while (!isEmpty(q)) {
        int currentVertex = dequeue(q);
        printf("Visited %d\n", currentVertex);

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

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

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

int main() {
    struct Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 5);
    addEdge(graph, 4, 5);

    printf("BFS starting from vertex 0:\n");
    bfs(graph, 0);

    // Free allocated memory
    for (int i = 0; i < graph->numVertices; i++) {
        struct Node* current = graph->adjLists[i];
        while (current) {
            struct Node* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->adjLists);
    free(graph->visited);
    free(graph);

    return 0;
}

Applications of BFS

BFS is a versatile algorithm with numerous applications:

  • Shortest Path in Unweighted Graphs: Since BFS explores layer by layer, it naturally finds the shortest path (in terms of number of edges) from a source to all other reachable nodes.
  • Web Crawlers: Search engines use BFS to traverse the web, starting from a seed URL and exploring all linked pages.
  • Social Networking: Finding people within 'k' degrees of separation.
  • Garbage Collection: Mark-and-sweep garbage collectors use BFS to identify reachable objects.
  • Network Broadcasting: Finding all reachable nodes in a network.
  • Maze Solving: Finding the shortest path through a maze.