大作业: 用c语言广度优先算法完成一个任务实现: 要求:用本科生大作业模板，需要有任务要求(结合算法自定)、程序实现(程序需要有中文注释)，实验结果

任务要求：使用广度优先算法实现图的遍历。

程序实现：我们先定义了一个结构体来表示图中的节点，包括节点编号和节点的邻接表。然后定义了一个队列来保存待遍历的节点，以及一个布尔型数组来标记每个节点是否被访问过。最后我们实现了广度优先遍历算法，具体注释见代码：

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

// 定义节点结构体
typedef struct node {
    int val; // 节点编号
    struct node* next; // 邻接表指针
} Node;

// 定义图结构体
typedef struct graph {
    int nv; // 节点数量
    Node** adjList; // 邻接表数组
} Graph;

// 定义队列结构体
typedef struct queue {
    int front, rear;
    int* arr; // 保存队列元素的数组
} Queue;

// 创建节点
Node* createNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// 创建图
Graph* createGraph(int nv) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->nv = nv;
    graph->adjList = (Node**)malloc(nv * sizeof(Node*));
    for (int i = 0; i < nv; i++) {
        graph->adjList[i] = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    Node* node = createNode(dest);
    node->next = graph->adjList[src];
    graph->adjList[src] = node;
}

// 创建队列
Queue* createQueue(int size) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = -1;
    queue->rear = -1;
    queue->arr = (int*)malloc(size * sizeof(int));
    return queue;
}

// 判断队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front == -1;
}

// 入队
void enqueue(Queue* queue, int val) {
    if (isQueueEmpty(queue)) {
        queue->front = 0;
    }
    queue->arr[++queue->rear] = val;
}

// 出队
int dequeue(Queue* queue) {
    int val = queue->arr[queue->front];
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    return val;
}

// 广度优先遍历
void bfs(Graph* graph, int start) {
    // 创建布尔型数组，标记节点是否被访问过
    bool* visited = (bool*)malloc(graph->nv * sizeof(bool));
    for (int i = 0; i < graph->nv; i++) {
        visited[i] = false;
    }

    // 创建队列，并将起始节点入队
    Queue* queue = createQueue(graph->nv);
    visited[start] = true;
    enqueue(queue, start);

    // 遍历队列中的节点
    while (!isQueueEmpty(queue)) {
        int current = dequeue(queue);
        printf("%d ", current);

        // 遍历当前节点的邻接表，并将未访问过的节点入队
        Node* temp = graph->adjList[current];
        while (temp) {
            int neighbor = temp->val;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                enqueue(queue, neighbor);
            }
            temp = temp->next;
        }
    }
}

int main() {
    // 创建一个包含5个节点的图
    Graph* graph = createGraph(5);

    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    // 广度优先遍历
    printf("BFS: ");
    bfs(graph, 2);

    return 0;
}

实验结果：运行程序后输出：BFS: 2 0 3 1