广度优先搜索遍历连通图C语言代码实现

广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或查找无向图或有向图中节点的有效算法。以下是使用C语言实现的简单BFS遍历连通图的示例：

#include <stdio.h>
#include <stdlib.h>
#define MAX 100 // 图的最大节点数

// 结构体表示图中的边和节点
typedef struct {
    int src;
    int dest;
} Edge;

// 用邻接表表示图
Edge graph[MAX][MAX];

// 初始队列结构，存储顶点
int queue[MAX], front = -1, rear = -1;

// 检查队列是否为空
bool isEmpty() {
    return (front == rear);
}

// 将元素添加到队列末尾
void enqueue(int item) {
    if (rear + 1 >= MAX)
        printf("Queue overflow\n");
    else {
        rear++;
        queue[rear] = item;
    }
}

// 从队列头部移除元素
int dequeue() {
    if (isEmpty())
        printf("Queue underflow\n");
    else {
        int item = queue[front];
        front++;
        return item;
    }
}

// 宽度优先搜索函数
void bfs(int start) {
    int i, j;
    queue[rear++] = start; // 入队

    while (!isEmpty()) {
        int vertex = dequeue(); // 出队
        printf("%d ", vertex); // 输出当前节点

        for (i = 0; i < MAX; i++) { // 遍历邻居
            if (graph[vertex][i].dest != -1 && graph[vertex][i].src != start) { // 如果邻居未访问过
                enqueue(graph[vertex][i].dest); // 将邻居入队
            }
        }
    }
}

int main() {
    // 初始化图，这里只示例了简单的邻接列表表示法
    int vertices = 5; // 图中节点数
    int edge_count = 4; // 边的数量
    int src, dest;

    // 连接图的边（这里省略实际输入）
    // ... (为图添加边)

    printf("Starting from node %d, BFS traversal:\n", start);
    bfs(start);

    return 0;
}

在这个例子中，我们首先创建了一个邻接表表示图，然后实现了宽度优先搜索的基本操作（enqueue、dequeue）。`bfs`函数从起点开始，每次出队一个节点并访问其所有未访问过的邻居，将它们入队继续处理。