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

struct node
{
    int vertex;
    struct node *next;
};

struct node *createnode(int val)
{
    struct node *new=malloc(sizeof(struct node));
    new->vertex=val;
    new->next=NULL;
    return new;
}

struct graph
{
    int no_of_vertices;
    struct node **adjlists;
    int *visited;
};

struct graph *creategraph(int vertices)
{
    struct graph *graph=malloc(sizeof(struct graph));
    graph->no_of_vertices=vertices;

    graph->adjlists=malloc(vertices * sizeof(struct node *));
    graph->visited=malloc(vertices * sizeof(int));

    int i;
    for(i=0; i<vertices; i++)
    {
        graph->adjlists[i]=NULL;
        graph->visited[i]=0;
    }

    return graph;
}

void addEdge(struct graph *graph, int source, int destination)
{
    struct node *new=createnode(destination);
    new->next=graph->adjlists[source];
    graph->adjlists[source]=new;

    new=createnode(source);
    new->next=graph->adjlists[destination];
    graph->adjlists[destination]=new;
}

void printgraph(struct graph *graph)
{
    int v;
    for(v=0; v<graph->no_of_vertices; v++)
    {
        struct node *temp=graph->adjlists[v];
        printf("\nelements adjacent to vertex %d\n", v);
        while(temp)
        {
            printf("%d ---> ", temp->vertex);
            temp=temp->next;
        }
        printf("\n");
    }
}

void bfs(struct graph *graph, int startvertex)
{
    struct node *queue=NULL;
    graph->visited[startvertex]=1;
    enqueue(&queue, startvertex);

    while(!isempty(queue))
    {
        printqueue(queue);
        int currentvertex=dequeue(&queue);
        printf("Visited %d ", currentvertex);

        struct node *temp=graph->adjlists[currentvertex];
        while(temp)
        {
            int adjvertex=temp->vertex;
            if(graph->visited[adjvertex]==0)
            {
                graph->visited[adjvertex]=1;
                enqueue(&queue, adjvertex);
            }
            temp=temp->next;
        }
    }
}

int isempty(struct node *queue)
{
    return queue==NULL;
}

void enqueue(struct node **queue, int value)
{
    struct node *new = createnode(value);
    if(isempty(*queue))
    {
        *queue=new;
    }
    else
    {
        struct node *temp=*queue;
        while(temp->next)
        {
            temp=temp->next;
        }
        temp->next=new;
    }
}

int dequeue(struct node **queue)
{
    int data = (*queue)->vertex;
    struct node *temp = *queue;
    *queue = (*queue)->next;
    free(temp);
    return data;
}

void printqueue(struct node *queue)
{
    while (queue)
    {
        printf("%d ", queue->vertex);
        queue = queue->next;
    }
    printf("\n");
}

int main(void)
{
    struct graph *graph = creategraph(6);
    printf("\nWhat do you want to do?\n");
    printf("1. Add edge\n");
    printf("2. Print graph\n");
    printf("3. BFS\n");
    printf("4. Exit\n");
    int choice;
    scanf("%d", &choice);
    while (choice != 4)
    {
        if (choice == 1)
        {
            int source, destination;
            printf("Enter source and destination: ");
            scanf("%d %d", &source, &destination);
            addEdge(graph, source, destination);
        }
        else if (choice == 2)
        {
            printgraph(graph);
        }
        else if (choice == 3)
        {
            int startvertex;
            printf("Enter starting vertex: ");
            scanf("%d", &startvertex);
            bfs(graph, startvertex);
        }
        else
        {
            printf("Invalid choice\n");
        }
        printf("What do you want to do?\n");
        printf("1. Add edge\n");
        printf("2. Print graph\n");
        printf("3. BFS\n");
        printf("4. Exit\n");
        scanf("%d", &choice);
    }
    return 0;
}