广度优先搜索邻接表C语言

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索树形和图形数据结构的算法。在C语言中，邻接表是一种常用的数据结构来表示图，它将每个节点的邻接节点存储在一个链表中，这使得BFS特别高效。

以下是使用C语言实现BFS邻接表的基本步骤：

1. 定义图和邻接表结构：

typedef struct Node {
    int data;
    struct List *adjacent; // 邻接列表
} Node;

typedef struct List {
    Node *head;
} List;

2. 初始化邻接表：

void initializeAdjacencyList(Node *node, List *list) {
    node->adjacent = (List*) malloc(sizeof(List));
    list->head = NULL;
}

3. 添加边（连接两个节点）：

void addEdge(Node *source, int dest, List **adjacent) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = dest;
    newNode->adjacent = NULL;

    if (*adjacent == NULL) {
        *adjacent = newNode;
    } else {
        Node *current = *adjacent;
        while (current->adjacent != NULL) {
            current = current->adjacent;
        }
        current->adjacent = newNode;
    }
}

4. 广度优先搜索函数（用队列实现）：

void bfs(Node *root, List **adjacent) {
    Queue *queue = createQueue(); // 创建队列
    Node *current = root;
    queue_enqueue(queue, current);

    while (!queue_isEmpty(queue)) {
        current = queue_dequeue(queue);
        printf("%d ", current->data); // 输出当前节点
        List *temp = current->adjacent;
        while (temp != NULL) {
            Node *neighbor = temp->head;
            queue_enqueue(queue, neighbor);
            temp = temp->adjacent;
        }
    }
    destroyQueue(queue);
}