C Data Structures: Graph Representations, BFS & DFS Traversals Masterclass

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

#define MAX_V 10

typedef struct EdgeNode {
    int to;
    struct EdgeNode *next;
} EdgeNode;

typedef struct {
    EdgeNode *adj[MAX_V];
    int V;
} Graph;

Graph *graph_create(int V) {
    Graph *g = calloc(1, sizeof(Graph));
    g->V = V;
    return g;
}

void graph_add_edge(Graph *g, int u, int v) {
    EdgeNode *e = malloc(sizeof(EdgeNode));
    e->to = v; e->next = g->adj[u]; g->adj[u] = e;
    /* Undirected: add reverse edge too */
    EdgeNode *e2 = malloc(sizeof(EdgeNode));
    e2->to = u; e2->next = g->adj[v]; g->adj[v] = e2;
}

void bfs(const Graph *g, int start) {
    int visited[MAX_V] = {0};
    int queue[MAX_V], front = 0, rear = 0;
    visited[start] = 1;
    queue[rear++] = start;
    printf("BFS from %d: ", start);
    while (front < rear) {
        int u = queue[front++];
        printf("%d ", u);
        for (EdgeNode *e = g->adj[u]; e; e = e->next) {
            if (!visited[e->to]) {
                visited[e->to] = 1;
                queue[rear++] = e->to;
            }
        }
    }
    printf("\n");
}

static int dfs_visited[MAX_V];
void dfs(const Graph *g, int u) {
    dfs_visited[u] = 1;
    printf("%d ", u);
    for (EdgeNode *e = g->adj[u]; e; e = e->next)
        if (!dfs_visited[e->to]) dfs(g, e->to);
}

int main(void) {
    Graph *g = graph_create(6);
    graph_add_edge(g, 0, 1);
    graph_add_edge(g, 0, 2);
    graph_add_edge(g, 1, 3);
    graph_add_edge(g, 2, 4);
    graph_add_edge(g, 3, 5);

    bfs(g, 0);

    memset(dfs_visited, 0, sizeof(dfs_visited));
    printf("DFS from 0: ");
    dfs(g, 0);
    printf("\n");
    return 0;
}