广度优先算法 C语言

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图（Graph）或树（Tree）数据结构的算法。它从根节点开始，首先访问所有邻居节点，然后再逐层向下访问，直到找到目标节点或遍历完整个图。以下是使用C语言实现广度优先搜索的示例代码：

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

#define MAX_VERTICES 100

// 定义邻接表节点
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 定义图结构
typedef struct Graph {
    int numVertices;
    Node** adjLists;
    bool* visited;
} Graph;

// 创建一个新的节点
Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 初始化图
Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = malloc(vertices * sizeof(bool));

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

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 从源节点到目标节点
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 从目标节点到源节点（如果是无向图）
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 广度优先搜索
void bfs(Graph* graph, int startVertex) {
    Node* queue[MAX_VERTICES];
    int front = 0;
    int rear = 0;

    graph->visited[startVertex] = true;
    queue[rear++] = createNode(startVertex);

    while (front < rear) {
        int currentVertex = queue[front]->vertex;
        printf("访问节点 %d\n", currentVertex);
        Node* temp = queue[front];
        free(temp);
        front++;

        Node* temp2 = graph->adjLists[currentVertex];

        while (temp2) {
            int adjVertex = temp2->vertex;

            if (!graph->visited[adjVertex]) {
                graph->visited[adjVertex] = true;
                queue[rear++] = createNode(adjVertex);
            }
            temp2 = temp2->next;
        }
    }
}

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 4, 5);

    bfs(graph, 0);

    return 0;
}

这段代码定义了一个简单的图结构，并实现了广度优先搜索算法。`createGraph`函数用于创建图，`addEdge`函数用于添加边，`bfs`函数实现了广度优先搜索算法。