C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Graph Traversal Algorithms — BFS (Breadth-First Search)

Breadth-First Search (BFS) using Adjacency List representation.

This algorithm is foundational for exploring graphs, finding shortest paths (in unweighted graphs), and is heavily used in real-world systems like social networks, GPS routing, and AI.

Graph Traversal — Breadth-First Search (BFS)

Concept Overview

Breadth-First Search (BFS) is a level-order traversal of a graph.

It explores:

  • All neighbors of a vertex before moving to the next level.
  • It uses a queue (FIFO) to track which vertex to visit next.

BFS Logic Step-by-Step

    1. Start from a source vertex (say start).

    2. Mark it as visited.

    3. Enqueue the source vertex.

    4. While the queue is not empty:

    • Dequeue a vertex v.
    • Visit all unvisited adjacent vertices of v and enqueue them.

Example Graph

0 — 1

|   |

2 — 3

Adjacency List:

0 → 1 → 2

1 → 0 → 3

2 → 0 → 3

3 → 1 → 2

BFS Traversal (starting from 0)

BFS: 0 → 1 → 2 → 3

 

C Program: Graph Traversal Algorithms — BFS (Breadth-First Search) using Adjacency List

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure for adjacency list node


struct Node {


    int vertex;


    struct Node* next;


};


 


// Structure for the graph


struct Graph {


    int vertices;


    struct Node** adjLists;


    int* visited;


};


 


// Queue structure for BFS


struct Queue {


    int items[100];


    int front;


    int rear;


};


 


// Function to create a new node


struct Node* createNode(int v) {


    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));


    newNode->vertex = v;


    newNode->next = NULL;


    return newNode;


}


 


// Function to create a graph


struct Graph* createGraph(int vertices) {


    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));


    graph->vertices = vertices;


 


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


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


 


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


        graph->adjLists[i] = NULL;


        graph->visited[i] = 0;


    }


 


    return graph;


}


 


// Add an edge (undirected)


void addEdge(struct Graph* graph, int src, int dest) {


    struct Node* newNode = createNode(dest);


    newNode->next = graph->adjLists[src];


    graph->adjLists[src] = newNode;


 


    newNode = createNode(src);


    newNode->next = graph->adjLists[dest];


    graph->adjLists[dest] = newNode;


}


 


// Create a queue


struct Queue* createQueue() {


    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));


    q->front = -1;


    q->rear = -1;


    return q;


}


 


// Queue operations


int isEmpty(struct Queue* q) {


    return q->rear == -1;


}


 


void enqueue(struct Queue* q, int value) {


    if (q->rear == 99)


        return;


    if (q->front == -1)


        q->front = 0;


    q->rear++;


    q->items[q->rear] = value;


}


 


int dequeue(struct Queue* q) {


    int item;


    if (isEmpty(q))


        return -1;


    item = q->items[q->front];


    q->front++;


    if (q->front > q->rear)


        q->front = q->rear = -1;


    return item;


}


 


// BFS traversal


void bfs(struct Graph* graph, int startVertex) {


    struct Queue* q = createQueue();


 


    graph->visited[startVertex] = 1;


    enqueue(q, startVertex);


 


    printf("BFS Traversal starting from vertex %d: ", startVertex);


 


    while (!isEmpty(q)) {


        int currentVertex = dequeue(q);


        printf("%d ", currentVertex);


 


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


 


        while (temp) {


            int adjVertex = temp->vertex;


            if (graph->visited[adjVertex] == 0) {


                graph->visited[adjVertex] = 1;


                enqueue(q, adjVertex);


            }


            temp = temp->next;


        }


    }


 


    printf("\n");


}


 


int main() {


    int vertices, edges;


    printf("Enter number of vertices: ");


    scanf("%d", &vertices);


 


    struct Graph* graph = createGraph(vertices);


 


    printf("Enter number of edges: ");


    scanf("%d", &edges);


 


    printf("Enter edges (u v):\n");


    for (int i = 0; i < edges; i++) {


        int u, v;


        scanf("%d %d", &u, &v);


        addEdge(graph, u, v);


    }


 


    int start;


    printf("Enter starting vertex for BFS: ");


    scanf("%d", &start);


 


    bfs(graph, start);


 


    return 0;


}

Output

 
INPUT :
Enter number of vertices: 4
Enter number of edges: 4
Enter edges (u v):
0 1
0 2
1 3
2 3
Enter starting vertex for BFS: 0

OUTPUT :
BFS Traversal starting from vertex 0: 0 1 2 3

Complexity Analysis

Operation

Time Complexity

Space Complexity

BFS Traversal

O(V + E)

O(V)
  • Every vertex and edge is processed once.
  • Queue and visited array take O(V) space.

Key Takeaways

  • BFS explores level by level (breadth-wise).
  • Uses a queue for tracking exploration order.
  • Works for both directed and undirected
  • Finds shortest paths in unweighted graphs.
  • Ideal for connected components, pathfinding, and network analysis.

 

Previous
Next