Implement BFT and DFT for given graph, when graph is represented by a) Adjacency Matrix b) Adjacency Lists

 #include <stdio.h>

#include <stdlib.h>

#define MAX 100

// ---------------- Common Queue for BFS ----------------

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

void enqueue(int val) {

    if (rear == MAX - 1) return;

    queue[++rear] = val;

    if (front == -1) front = 0;

}

int dequeue() {

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

    return queue[front++];

}

int isQueueEmpty() {

    return front == -1 || front > rear;

}

// ---------------- A. Adjacency Matrix ----------------

int visited[MAX];

void BFS_matrix(int adj[MAX][MAX], int n, int start) {

    for (int i = 0; i < n; i++) visited[i] = 0;

    enqueue(start);

    visited[start] = 1;

    printf("BFS (Adjacency Matrix): ");

    while (!isQueueEmpty()) {

        int node = dequeue();

        printf("%d ", node);

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

            if (adj[node][i] && !visited[i]) {

                enqueue(i);

                visited[i] = 1;

            }

        }

    }

    printf("\n");

}

void DFS_matrix_util(int adj[MAX][MAX], int n, int v) {

    visited[v] = 1;

    printf("%d ", v);

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

        if (adj[v][i] && !visited[i]) {

            DFS_matrix_util(adj, n, i);

        }

    }

}

void DFS_matrix(int adj[MAX][MAX], int n, int start) {

    for (int i = 0; i < n; i++) visited[i] = 0;

    printf("DFS (Adjacency Matrix): ");

    DFS_matrix_util(adj, n, start);

    printf("\n");

}

// ---------------- B. Adjacency List ----------------

struct Node {

    int vertex;

    struct Node* next;

};

struct Node* adjList[MAX];

void addEdge_list(int u, int v) {

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

    newNode->vertex = v;

    newNode->next = adjList[u];

    adjList[u] = newNode;

}

void BFS_list(int n, int start) {

    for (int i = 0; i < n; i++) visited[i] = 0;

    front = rear = -1;

    enqueue(start);

    visited[start] = 1;

    printf("BFS (Adjacency List): ");

    while (!isQueueEmpty()) {

        int node = dequeue();

        printf("%d ", node);

        struct Node* temp = adjList[node];

        while (temp) {

            if (!visited[temp->vertex]) {

                enqueue(temp->vertex);

                visited[temp->vertex] = 1;

            }

            temp = temp->next;

        }

    }

    printf("\n");

}

void DFS_list_util(int v) {

    visited[v] = 1;

    printf("%d ", v);

    struct Node* temp = adjList[v];

    while (temp) {

        if (!visited[temp->vertex]) {

            DFS_list_util(temp->vertex);

        }

        temp = temp->next;

    }

}

void DFS_list(int n, int start) {

    for (int i = 0; i < n; i++) visited[i] = 0;

    printf("DFS (Adjacency List): ");

    DFS_list_util(start);

    printf("\n");

}

// ---------------- Main ----------------

int main() {

    int n = 5; // number of vertices

    int adj[MAX][MAX] = {0}; // adjacency matrix

    // Sample edges

    int edges[][2] = {{0,1},{0,2},{1,2},{1,3},{3,4}};

    int edgeCount = sizeof(edges)/sizeof(edges[0]);

    // Build Adjacency Matrix and List

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

        int u = edges[i][0];

        int v = edges[i][1];

        adj[u][v] = 1;

        adj[v][u] = 1; // undirected graph

        addEdge_list(u, v);

        addEdge_list(v, u);

    }

    int start = 0; // start vertex

    BFS_matrix(adj, n, start);

    DFS_matrix(adj, n, start);

    BFS_list(n, start);

    DFS_list(n, start);

    return 0;

}

Output: