数据结构c语言图的广度优先搜索算法

广度优先搜索算法（BFS）是一种基于图的遍历算法，它从一个起点开始，依次访问与起点相邻的节点，然后再访问与这些节点相邻的节点，以此类推，直到遍历完所有的节点。

下面是使用C语言实现图的广度优先搜索算法的代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
#define MAX_QUEUE_SIZE 100

typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 图的顶点
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 图的边
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

typedef struct {
    int data[MAX_QUEUE_SIZE]; // 队列数据
    int front; // 队首
    int rear; // 队尾
} Queue;

void initGraph(Graph *G) {
    int i, j;
    printf("请输入图的顶点数：");
    scanf("%d", &(G->vertex_num));
    printf("请输入图的边数：");
    scanf("%d", &(G->edge_num));
    for (i = 0; i < G->vertex_num; i++) {
        printf("请输入第%d个顶点：", i + 1);
        scanf("%d", &(G->vertex[i]));
    }
    for (i = 0; i < G->vertex_num; i++) {
        for (j = 0; j < G->vertex_num; j++) {
            G->edges[i][j] = 0;
        }
    }
    for (i = 0; i < G->edge_num; i++) {
        int v1, v2;
        printf("请输入第%d条边的顶点序号：", i + 1);
        scanf("%d%d", &v1, &v2);
        G->edges[v1 - 1][v2 - 1] = G->edges[v2 - 1][v1 - 1] = 1;
    }
}

void initQueue(Queue *Q) {
    Q->front = Q->rear = 0;
}

int isQueueEmpty(Queue *Q) {
    return Q->front == Q->rear;
}

int isQueueFull(Queue *Q) {
    return (Q->rear + 1) % MAX_QUEUE_SIZE == Q->front;
}

void enQueue(Queue *Q, int data) {
    if (isQueueFull(Q)) {
        printf("队列已满！\n");
        return;
    }
    Q->data[Q->rear] = data;
    Q->rear = (Q->rear + 1) % MAX_QUEUE_SIZE;
}

int deQueue(Queue *Q) {
    if (isQueueEmpty(Q)) {
        printf("队列已空！\n");
        return -1;
    }
    int data = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_QUEUE_SIZE;
    return data;
}

void BFS(Graph *G, int vertex) {
    Queue Q;
    int i, j;
    int visited[MAX_VERTEX_NUM] = {0}; // 标记顶点是否被访问过
    initQueue(&Q);
    printf("%d ", G->vertex[vertex]);
    visited[vertex] = 1;
    enQueue(&Q, vertex);
    while (!isQueueEmpty(&Q)) {
        int v = deQueue(&Q);
        for (i = 0; i < G->vertex_num; i++) {
            if (G->edges[v][i] == 1 && visited[i] == 0) {
                printf("%d ", G->vertex[i]);
                visited[i] = 1;
                enQueue(&Q, i);
            }
        }
    }
}

int main() {
    Graph G;
    initGraph(&G);
    printf("请输入起始顶点：");
    int vertex;
    scanf("%d", &vertex);
    printf("广度优先搜索结果：");
    BFS(&G, vertex - 1);
    printf("\n");
    return 0;
}

这段代码首先定义了一个图的结构体 `Graph` 和一个队列的结构体 `Queue`，然后实现了初始化图、初始化队列、判断队列是否为空、判断队列是否已满、入队、出队以及广度优先搜索算法的函数。

在 `main` 函数中，先调用 `initGraph` 函数初始化图，然后输入起始顶点，最后调用 `BFS` 函数进行广度优先搜索，并输出结果。