按广度优先非递归遍历图G。使用辅助队列Q 和访问标志数组visited （参考实验三中的LinkQueueDef.h 和LinkQueueAlgo.h）

以下是基于邻接表表示的图G的广度优先非递归遍历算法，使用辅助队列Q和访问标志数组visited：

#include <stdio.h>
#include <stdbool.h>
#include "LinkQueueDef.h"
#include "LinkQueueAlgo.h"

#define MAX_VERTEX_NUM 20 // 最多顶点数

// 边表结点
typedef struct ArcNode {
    int adjvex; // 邻接点在顶点数组中的下标
    struct ArcNode* nextarc; // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结点
typedef struct VNode {
    char data; // 顶点数据
    ArcNode* firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图
typedef struct {
    AdjList vertices; // 顶点表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化图
bool InitALGraph(ALGraph* G) {
    printf("请输入顶点数和边数:\n");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    if (G->vexnum > MAX_VERTEX_NUM) {
        printf("顶点数超过最大限制!\n");
        return false;
    }
    printf("请输入顶点数据:\n");
    for (int i = 0; i < G->vexnum; i++) {
        scanf(" %c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入边:\n");
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        printf("请输入第%d条边的两个顶点下标:\n", i + 1);
        scanf("%d%d", &v1, &v2);
        if (v1 < 0 || v1 >= G->vexnum || v2 < 0 || v2 >= G->vexnum) {
            printf("顶点下标越界!\n");
            return false;
        }
        ArcNode* arc1 = (ArcNode*)malloc(sizeof(ArcNode));
        arc1->adjvex = v2;
        arc1->nextarc = G->vertices[v1].firstarc;
        G->vertices[v1].firstarc = arc1;
        ArcNode* arc2 = (ArcNode*)malloc(sizeof(ArcNode));
        arc2->adjvex = v1;
        arc2->nextarc = G->vertices[v2].firstarc;
        G->vertices[v2].firstarc = arc2;
    }
    return true;
}

// 广度优先非递归遍历
void BFS(ALGraph G, int v, bool visited[]) {
    LinkQueue Q;
    InitQueue(&Q); // 初始化队列
    printf("%c ", G.vertices[v].data); // 访问初始顶点v
    visited[v] = true; // 标记v已访问
    EnQueue(&Q, v); // v入队列
    while (!QueueEmpty(Q)) { // 队列不空
        int u;
        DeQueue(&Q, &u); // 队头元素出队列并赋值给u
        ArcNode* arc = G.vertices[u].firstarc;
        while (arc) { // 枚举u的所有邻接点
            int w = arc->adjvex;
            if (!visited[w]) { // w未访问
                printf("%c ", G.vertices[w].data); // 访问顶点w
                visited[w] = true; // 标记w已访问
                EnQueue(&Q, w); // w入队列
            }
            arc = arc->nextarc;
        }
    }
    printf("\n");
}

// 测试
int main() {
    ALGraph G;
    if (InitALGraph(&G)) {
        bool visited[MAX_VERTEX_NUM] = { false }; // 标记数组初始化为false
        printf("广度优先非递归遍历结果为:\n");
        for (int i = 0; i < G.vexnum; i++) {
            if (!visited[i]) { // i未访问
                BFS(G, i, visited); // 从i开始遍历
            }
        }
    }
    return 0;
}

其中，LinkQueueDef.h 和 LinkQueueAlgo.h 分别是链式队列的定义和实现文件，可以从我的 GitHub 仓库中下载：https://github.com/wangzheng0822/algo/blob/master/c/linkqueue/LinkQueue.h