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

#define MAX_VERTICES 5  // 图的最大顶点数

// 图的邻接矩阵表示
int graph[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 1, 0, 0},
    {1, 0, 1, 1, 0},
    {1, 1, 0, 0, 1},
    {0, 1, 0, 0, 1},
    {0, 0, 1, 1, 0}
};

bool visited[MAX_VERTICES];  // 访问标记数组，用来记录哪些节点已经被访问过

// 队列结构
typedef struct {
    int items[MAX_VERTICES];  // 队列的数组表示
    int front;  // 队列的前端
    int rear;   // 队列的尾端
} Queue;

// 队列操作函数

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = -1;  // 队列初始化为空
}

// 检查队列是否为空
int isEmpty(Queue *q) {
    return q->front > q->rear;
}

// 入队操作
void enqueue(Queue *q, int value) {
    if (q->rear < MAX_VERTICES - 1) {  // 如果队列未满
        q->items[++(q->rear)] = value;  // 将新元素添加到队列的尾端
    }
}

// 出队操作
int dequeue(Queue *q) {
    if (!isEmpty(q)) {
        return q->items[(q->front)++];  // 从队列的前端取出一个元素
    }
    return -1;  // 队列为空时返回 -1
}

// 广度优先遍历 BFS 函数
void bfs(int start, int n) {
    Queue q;
    initQueue(&q);  // 初始化队列
    
    enqueue(&q, start);  // 将起始节点入队
    visited[start] = true;  // 标记起始节点已访问

    while (!isEmpty(&q)) {  // 队列不为空时，继续遍历
        int current = dequeue(&q);  // 从队列中取出一个节点
        printf("%d ", current);  // 输出当前节点

        // 遍历当前节点的所有邻接节点
        for (int i = 0; i < n; i++) {
            if (graph[current][i] == 1 && !visited[i]) {  // 如果当前节点和 i 节点之间有边且 i 节点未被访问
                enqueue(&q, i);  // 将 i 节点入队
                visited[i] = true;  // 标记 i 节点已访问
            }
        }
    }
}

int main() {
    int n = MAX_VERTICES;  // 图的顶点数
    for (int i = 0; i < n; i++) {
        visited[i] = false;  // 初始化访问标记数组，将所有节点标记为未访问
    }

    printf("广度优先遍历（BFS）：\n");
    bfs(0, n);  // 从顶点 0 开始进行 BFS 遍历
    printf("\n");

    return 0;
}