BFS

// BFS
// 薯妮亞Patata
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Graph Node
typedef struct sNode {
    int vertex;
    struct sNode* next;
} GNode;

// Graph
typedef struct sGraph {
    GNode** adjLists;
    int numVertices;
    int* visited;
} Graph;

// Graph operation
Graph* CreateGraph(int vertices);
void AddEdge(Graph* graph, int src, int dest);
void PrintGraph(Graph* graph);

// Queue Node
typedef struct sNode1 {
    int data;
    struct sNode1 *next;
} QNode;

// Queue
typedef struct sQueue {
    QNode *front, *rear;
} Queue;

// Queue operation 
Queue* CreateQueue(void);
    // constructor
void DeleteQueue(Queue* queue);
    // destrcutor, not automatically triggered like c++
bool IsEmpty(Queue* queue);
    // return true if stack is empty
void Push(Queue* queue, int item);
    // add an element at the top
void Pop(Queue* queue);
    // delete top element
int Front(Queue* queue);
    // return front element of queue
int Rear(Queue* queue);
    // return rear element of queue
int Size(Queue* queue);
    // return size of queue
void PrintQueue(Queue* queue);
    // print from front to rear

// BFS
void BFS(Graph* graph, int startVertex);

int main(void)
{
    Graph* graph = CreateGraph(8);

    AddEdge(graph, 0, 1);    AddEdge(graph, 1, 0);
    AddEdge(graph, 0, 2);    AddEdge(graph, 2, 0);
    AddEdge(graph, 1, 3);    AddEdge(graph, 3, 1);
    AddEdge(graph, 1, 4);    AddEdge(graph, 4, 1);
    AddEdge(graph, 2, 5);    AddEdge(graph, 5, 2);
    AddEdge(graph, 2, 6);    AddEdge(graph, 6, 2);
    AddEdge(graph, 3, 7);    AddEdge(graph, 7, 3);
    AddEdge(graph, 4, 7);    AddEdge(graph, 7, 4);
    AddEdge(graph, 5, 7);    AddEdge(graph, 7, 5);
    AddEdge(graph, 6, 7);    AddEdge(graph, 7, 6);

    BFS(graph, 0);

    return 0;
}

// BFS
void BFS(Graph* graph, int startVertex)
{
    int currentVertex;
    int adjVertex;
    Queue *queue = CreateQueue();
    GNode *temp;

    graph->visited[startVertex] = 1;
    Push(queue, startVertex);

    while (!IsEmpty(queue)) {
        printf("Queue: "); PrintQueue(queue);

        currentVertex = Front(queue); Pop(queue);
        printf("Visited %d\n", currentVertex);

        temp = graph->adjLists[currentVertex];
        while (temp != NULL) {
            adjVertex = temp->vertex;
            if (graph->visited[adjVertex] == 0) {
                graph->visited[adjVertex] = 1;
                Push(queue, adjVertex);
            }
            temp = temp->next;
        }
    }
}

// Create a node
GNode* CreateNode(int v)
{
    GNode* newNode = malloc(sizeof(GNode));

    newNode->vertex = v;
    newNode->next = NULL;
    
    return newNode;
}

// Create graph
Graph* CreateGraph(int vertices)
{
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    int i;

    graph->adjLists = (GNode**)calloc(vertices, sizeof(GNode*));
    graph->numVertices = vertices;
    graph->visited = (int*)calloc(vertices, sizeof(int));

    return graph;
}

// Add edge
void AddEdge(Graph* graph, int src, int dest)
{
    GNode* newNode = malloc(sizeof(GNode));

    // Add edge from src to dest
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

// Print the graph
void PrintGraph(Graph* graph)
{
    int v;
    GNode* temp;

    for (v = 0; v < graph->numVertices; v++) {
        temp = graph->adjLists[v];
        while (temp != NULL) temp = temp->next;
    }
}

// constructor
Queue* CreateQueue(void)
{
    Queue* queue = (Queue*)malloc(sizeof(Queue));

    queue->front = NULL;
    queue->rear = NULL;

    return queue;
}

// destrcutor
void DeleteQueue(Queue* queue)
{
    while (!IsEmpty(queue)) {
        Pop(queue);
    }
    free(queue);
}

// return true if queue is empty
bool IsEmpty(Queue* queue)
{
    return queue->front == NULL;
}

// add an element at the end of the queue
void Push(Queue* queue, int item)
{
    QNode* newNode = (QNode*)malloc(sizeof(QNode));

    newNode->data = item;
    newNode->next = NULL;

    if (IsEmpty(queue)) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

// delete the front element of the queue
void Pop(Queue* queue)
{
    if (!IsEmpty(queue)) {
        QNode *temp = queue->front;

        queue->front = queue->front->next;
        free(temp);
    }
}

// return front element of queue
int Front(Queue* queue)
{
    return queue->front->data;
}

// return rear element of queue
int Rear(Queue* queue)
{
    return queue->rear->data;
}

// return size of queue
int Size(Queue* queue)
{
    QNode *temp;
    int count = 0;

    for (temp = queue->front; temp != NULL; temp = temp->next) {
        count++;
    }

    return count;
}

// print from front to rear
void PrintQueue(Queue* queue)
{
    QNode *current = queue->front;

    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}