广度优先算法c语言实现

以下是广度优先算法的C语言实现：

#include <stdio.h>
#define MAX_SIZE 100

// 定义队列结构
typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判断队列是否为空
int isEmpty(Queue *q) {
    return q->front == q->rear;
}

// 入队
void enqueue(Queue *q, int value) {
    q->data[q->rear] = value;
    q->rear++;
}

// 出队
int dequeue(Queue *q) {
    int value = q->data[q->front];
    q->front++;
    return value;
}

// 广度优先遍历
void breadthFirstSearch(int graph[][MAX_SIZE], int vertex, int start) {
    int visited[MAX_SIZE] = {0}; // 记录顶点是否被访问过
    Queue q;
    initQueue(&q);
    
    visited[start] = 1; // 标记起始顶点为已访问
    enqueue(&q, start); // 将起始顶点入队
    
    while (!isEmpty(&q)) {
        int current = dequeue(&q); // 出队一个顶点
        printf("%d ", current); // 输出当前顶点
        
        // 遍历与当前顶点相邻的顶点
        for (int i = 0; i < vertex; i++) {
            if (graph[current][i] == 1 && visited[i] == 0) {
                visited[i] = 1; // 标记相邻顶点为已访问
                enqueue(&q, i); // 将相邻顶点入队
            }
        }
    }
}

int main() {
    int vertex; // 顶点数
    int start; // 起始顶点
    int graph[MAX_SIZE][MAX_SIZE]; // 图的邻接矩阵表示
    
    printf("请输入顶点数：");
    scanf("%d", &vertex);
    
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < vertex; i++) {
        for (int j = 0; j < vertex; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    
    printf("请输入起始顶点：");
    scanf("%d", &start);
    
    printf("广度优先遍历结果：");
    breadthFirstSearch(graph, vertex, start);
    
    return 0;
}