#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 100
// Adjacency matrix for graph representation
int graph[MAX][MAX];
bool visited[MAX];
int queue[MAX], front = -1, rear = -1;

// Function to add an edge to the graph
void addEdge(int u, int v) {
    graph[u][v] = 1; // For directed graph
    graph[v][u] = 1; // Uncomment for undirected graph
}

// Function for DFS traversal
void dfs(int node, int vertices) {
    printf("%d ", node);
    visited[node] = true;
    for (int i = 0; i < vertices; i++) {
        if (graph[node][i] && !visited[i]) {
            dfs(i, vertices);
        }
    }
}

// Function to enqueue for BFS
void enqueue(int value) {
    if (rear == MAX - 1) return;
    if (front == -1) front = 0;
    queue[++rear] = value;
}

// Function to dequeue for BFS
int dequeue() {
    if (front == -1 || front > rear) return -1;
    return queue[front++];
}

// Function for BFS traversal
void bfs(int start, int vertices) {
    for (int i = 0; i < vertices; i++) visited[i] = false;
    enqueue(start);
    visited[start] = true;
    while (front <= rear) {
        int node = dequeue();
        printf("%d ", node);
        for (int i = 0; i < vertices; i++) {
            if (graph[node][i] && !visited[i]) {
                enqueue(i);
                visited[i] = true;
            }
        }
    }
}

// Main function
int main() {
    int vertices = 5;

    // Initialize graph
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            graph[i][j] = 0;
        }
    }

    // Initialize visited array
    for (int i = 0; i < MAX; i++) {
        visited[i] = false;
    }

    // Adding edges
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(1, 4);

    printf("DFS Traversal starting from node 0:\n");
    dfs(0, vertices);

    printf("\n\nBFS Traversal starting from node 0:\n");
    bfs(0, vertices);

    return 0;
}