图的BFS队列模板邻接矩阵c++实现

下面是基于邻接矩阵的BFS队列模板的C语言实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef int VertexType; // 顶点的数据类型

typedef struct {
    int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 顶点数、边数
    VertexType vexs[MAX_VERTEX_NUM]; // 顶点数组
} MGraph;

typedef struct {
    int data[MAX_VERTEX_NUM]; // 存放顶点下标
    int front, rear; // 队头、队尾指针
} Queue;

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

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

int EnQueue(Queue* Q, int x) { // 入队
    if ((Q->rear + 1) % MAX_VERTEX_NUM == Q->front) {
        return 0; // 队列已满
    }
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAX_VERTEX_NUM;
    return 1;
}

int DeQueue(Queue* Q, int* x) { // 出队
    if (Q->front == Q->rear) {
        return 0; // 队列已空
    }
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_VERTEX_NUM;
    return 1;
}

void CreateMGraph(MGraph* G) { // 创建无向图的邻接矩阵
    int i, j, k;
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入顶点数据：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            G->edges[i][j] = 0; // 初始化邻接矩阵
        }
    }
    printf("请输入边的信息：\n");
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条边的下标：", k + 1);
        scanf("%d %d", &i, &j);
        G->edges[i][j] = G->edges[j][i] = 1; // 无向图邻接矩阵对称
    }
}

void BFS(MGraph* G, int v) { // BFS遍历
    int visited[MAX_VERTEX_NUM] = {0}; // 访问标记数组
    Queue Q;
    int i, j;
    InitQueue(&Q); // 初始化队列
    visited[v] = 1; // 标记第v个顶点已访问
    printf("%d ", G->vexs[v]); // 访问第v个顶点
    EnQueue(&Q, v); // 第v个顶点入队
    while (!IsEmpty(&Q)) {
        DeQueue(&Q, &i); // 队头元素出队并赋值给i
        for (j = 0; j < G->vexnum; j++) {
            if (G->edges[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1; // 标记第j个顶点已访问
                printf("%d ", G->vexs[j]); // 访问第j个顶点
                EnQueue(&Q, j); // 第j个顶点入队
            }
        }
    }
}

int main() {
    MGraph G;
    CreateMGraph(&G);
    printf("BFS遍历结果为：");
    BFS(&G, 0);
    return 0;
}