Graphs - BFS

 

What is a Graph?

• A Graph is a collection of nodes (called vertices) connected by edges.

• Graphs can be:

  • Undirected (edges have no direction) or

  • Directed (Digraph) (edges have a direction).

• Graphs can be weighted (edges have weights/costs) or unweighted.

How to Represent a Graph in Computers?

Main ways to represent:

1. Adjacency Matrix:

• A 2D array G[V][V] where V = number of vertices.

• G[i][j] = 1 if there is an edge between vertex i and j, else 0.

• Good for dense graphs.

1. Adjacency List:

• An array of lists.

• Each element (vertex) points to a list of vertices it is connected to.

• Good for sparse graphs (uses less memory).

Algorithms for Graph Traversal

Two popular traversals:

Traversal	Meaning	Method
BFS (Breadth-First Search)	Visit neighbors level by level	Queue
DFS (Depth-First Search)	Explore as deep as possible before backtracking	Stack or Recursion

BFS (Breadth-First Search) Algorithm

Idea / Intuition

• BFS explores a graph level by level (breadth-wise).

• It visits all neighbors of a vertex before going deeper.

👉 BFS uses a queue to ensure nodes are processed in the order they are discovered.

Input: Graph, Starting Vertex
Output: Traverse graph level-wise

Algorithm:

1. Create a queue and enqueue the starting vertex.

2. Mark the starting vertex as visited.

3. While the queue is not empty:

• Dequeue a vertex and process it.

• Enqueue all its adjacent (unvisited) vertices.

• Mark them as visited.

Pseudo code:

BFS(start)

    mark start as visited

    enqueue(start)

    while queue is not empty:

        v = dequeue()

        for each neighbor u of v:

            if u is not visited:

                mark u as visited

                enqueue(u)

Example:

Output: [0, 1, 2, 3, 4]
Explanation: Starting from 0, the BFS traversal will follow these steps:
Visit 0 → Output: [0]
Visit 1 (first neighbor of 0) → Output: [0, 1]
Visit 2 (next neighbor of 0) → Output: [0, 1, 2]
Visit 3 (next neighbor of 1) → Output: [0, 1, 2, 3]
Visit 4 (neighbor of 2) → Final Output: [0, 1, 2, 3, 4]

Time Complexity Analysis

Let:

• $V$ = number of vertices

• $E$ = number of edges

Case 1: Adjacency Matrix Representation

• For each vertex, check all other vertices → $O(V).$

• For all $V$ vertices → $O(V^2)$.

Case 2: Adjacency List Representation

• Each vertex enqueued/dequeued once → $O(V)$.

• Each edge examined once (undirected, twice) → $O(E)$.

• Total complexity → $O(V + E)$.

👉 Adjacency list is more efficient for sparse graphs.

---

Space Complexity

• Space for visited array: $O(V)$.

• Space for queue: up to $O(V)$ in worst case.

• Total: $O(V)$.

C Program- BFS in Graph

#include<stdio.h>

#include<stdlib.h>

int queue[100], front = -1, rear = -1;

int visited[100];

// Enqueue

void enqueue(int value) {

    if (rear == 99)

        printf("Queue Overflow\n");

    else {

        if (front == -1)

            front = 0;

        queue[++rear] = value;

    }

}

// Dequeue

int dequeue() {

    if (front == -1 || front > rear)

        return -1;

    return queue[front++];

}

// BFS Function

void bfs(int adj[10][10], int start, int n) {

    int i;

    enqueue(start);

    visited[start] = 1;

    printf("BFS Traversal: ");

    

    while (front <= rear) {

        int current = dequeue();

        printf("%d ", current);

        

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

            if (adj[current][i] == 1 && !visited[i]) {

                enqueue(i);

                visited[i] = 1;

            }

        }

    }

}

int main() {

    int n, adj[10][10], i, j, start;

    printf("Enter number of vertices: ");

    scanf("%d", &n);

    

    printf("Enter adjacency matrix:\n");

    for (i=0; i<n; i++)

        for (j=0; j<n; j++)

            scanf("%d", &adj[i][j]);

            

    printf("Enter starting vertex (0 to %d): ", n-1);

    scanf("%d", &start);

    

    bfs(adj, start, n);

    

    return 0;

}

Enter number of vertices: 5

Enter adjacency matrix:

0 1 1 0 0

1 0 1 1 0

1 1 0 0 1

0 1 0 0 1

0 0 1 1 0

Enter starting vertex (0 to 4): 0

BFS Traversal: 0 1 2 3 4 

Linked Implementation Using Adjacency List

#include <stdio.h>

#include <stdlib.h>

#define MAX 100

// Node structure for adjacency list

typedef struct Node {

    int vertex;

    struct Node* next;

} Node;

// Graph structure

typedef struct Graph {

    int numVertices;

    Node** adjLists; // array of adjacency lists

    int* visited;    // visited array

} Graph;

// Queue structure for BFS

typedef struct Queue {

    int items[MAX];

    int front, rear;

} Queue;

// Function to create a queue

Queue* createQueue() {

    Queue* q = (Queue*)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 == MAX - 1)

        printf("Queue is full\n");

    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\n");

        item = -1;

    } else {

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

        q->front++;

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

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

        }

    }

    return item;

}

// Function to create a new node

Node* createNode(int v) {

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

    newNode->vertex = v;

    newNode->next = NULL;

    return newNode;

}

// Function to create a graph

Graph* createGraph(int vertices) {

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

    graph->numVertices = vertices;

    graph->adjLists = (Node**)malloc(vertices * sizeof(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 edge (undirected 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

    newNode = createNode(src);

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

    graph->adjLists[dest] = newNode;

}

// BFS traversal

void BFS(Graph* graph, int startVertex) {

    Queue* q = createQueue();

    graph->visited[startVertex] = 1;

    enqueue(q, startVertex);

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

    while (!isEmpty(q)) {

        int currentVertex = dequeue(q);

        printf("%d ", currentVertex);

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

        while (temp) {

            int adjVertex = temp->vertex;

            if (!graph->visited[adjVertex]) {

                graph->visited[adjVertex] = 1;

                enqueue(q, adjVertex);

            }

            temp = temp->next;

        }

    }

    printf("\n");

}

// Driver program

int main() {

    int vertices = 6;

    Graph* graph = createGraph(vertices);

    addEdge(graph, 0, 2);

    addEdge(graph, 0, 1);

    addEdge(graph, 1, 4);

    addEdge(graph, 1, 3);

    addEdge(graph, 2, 4);

    addEdge(graph, 3, 5);

    addEdge(graph, 4, 5);

    BFS(graph, 0);

    return 0;

}

BFS Traversal starting from vertex 0:

0 1 2 3 4 5