广度优先遍历例题c语言

广度优先遍历(Breadth-First Search, BFS)是一种用于图或树的数据结构搜索算法，它按照从上到下、从左到右的顺序逐层访问节点。下面是一个简单的用C语言实现的广度优先遍历的例子，假设我们要在一个无向图中查找两个顶点之间的最短路径：

#include <stdio.h>
#include <stdlib.h> // 需要包含队列操作的头文件

typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* newNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 初始化队列
void initializeQueue(Node** head_ref) {
    *head_ref = NULL;
}

// 添加元素到队列
void enqueue(Node** head_ref, Node* new_node) {
    if (*head_ref == NULL) {
        *head_ref = new_node;
    } else {
        Node* last = *head_ref;
        while (last->next != NULL)
            last = last->next;
        last->next = new_node;
    }
}

// 删除并返回队首元素
Node* dequeue(Node** head_ref) {
    if (*head_ref == NULL)
        return NULL;
    Node* temp = *head_ref;
    *head_ref = (*head_ref)->next;
    free(temp);
    return temp;
}

// 宽度优先遍历
void bfs(int graph[][], int V, int start, bool visited[]) {
    Node* queue = NULL;
    Node* front = NULL; // 指针指向队列头部
    visited[start] = true; // 标记起始节点已访问
    enqueue(&queue, newNode(start)); // 将起始节点放入队列

    while (queue != NULL) {
        Node* temp = dequeue(&queue); // 取出队首节点
        printf("%d ", temp->data);

        // 访问所有邻接节点
        for (int i = 0; i < V; i++) {
            if (graph[temp->data][i] && !visited[i]) {
                visited[i] = true; // 标记邻居已访问
                enqueue(&queue, newNode(i)); // 将邻居加入队列
            }
        }
    }
}

int main() {
    int graph[5][5] = { {0, 1, 0, 0, 0},
                        {1, 0, 1, 1, 0},
                        {0, 1, 0, 1, 1},
                        {0, 1, 1, 0, 1},
                        {0, 0, 1, 1, 0} };
    int V = sizeof(graph) / sizeof(graph[0]);
    int start = 0; // 起始节点
    bool visited[V]; // 初始化所有节点为未访问

    printf("BFS from node %d: \n", start);
    bfs(graph, V, start, visited);
    return 0;
}

这个例子中，`graph[][]`是一个邻接矩阵表示的图，`bfs`函数就是实现广度优先遍历的核心部分。在这个例子中，我们会找到起始节点0到图中其他所有节点的最短路径。