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

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.

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;

}