C语言完成以下广度优先搜索生成树代码 题目描述 由一张图经过广度优先搜索生成一棵树（第一被访问的顶点是生成图时第一个输入的顶点） 注：如生成的不是一棵树，则直接返回ERROR；否则返回树枝信息。 输入 vexnum //顶点总数 A B C D E F G H //顶点显示的数据 arcnum //边的总数 A,B A,C B,D B,E C,F C,G F,G D,H E,H 输出 A,B //显示树枝 A,C B,D B,E C,F C,G D,H

以下是C语言代码实现：

#include <stdio.h>
#include <stdbool.h>

// 定义邻接矩阵的最大大小
#define MAX_VERTEX_NUM 20

// 定义数据类型
typedef char VertexType;
typedef int EdgeType;

// 定义图的结构体
typedef struct {
    VertexType vexs[MAX_VERTEX_NUM]; // 存储顶点
    EdgeType arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存储边
    int vexnum, arcnum; // 存储顶点数和边数
} MGraph;

// 定义队列结构体
typedef struct {
    int data[MAX_VERTEX_NUM]; // 存储队列元素
    int front, rear; // 队首和队尾指针
} Queue;

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

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

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

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

// 广度优先搜索
bool BFS(MGraph *G, int start, int visited[MAX_VERTEX_NUM]) {
    Queue q;
    InitQueue(&q);
    EnQueue(&q, start);
    visited[start] = true;
    while (!QueueIsEmpty(&q)) {
        int v = DeQueue(&q);
        for (int w = 0; w < G->vexnum; w++) {
            if (G->arc[v][w] && !visited[w]) {
                visited[w] = true;
                EnQueue(&q, w);
            }
        }
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

// 生成树并输出树枝信息
void CreateTree(MGraph *G) {
    int visited[MAX_VERTEX_NUM] = {0};
    int count = 0;
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) {
            if (BFS(G, i, visited)) {
                count++;
                if (count == 1) {
                    printf("%c", G->vexs[i]);
                } else {
                    printf(" %c", G->vexs[i]);
                }
                for (int j = 0; j < G->vexnum; j++) {
                    if (visited[j] && G->arc[i][j]) {
                        printf(",%c", G->vexs[j]);
                    }
                }
                printf("\n");
            } else {
                printf("ERROR\n");
                return;
            }
        }
    }
}

int main() {
    MGraph G;
    scanf("%d", &G.vexnum);
    for (int i = 0; i < G.vexnum; i++) {
        scanf(" %c", &G.vexs[i]);
    }
    scanf("%d", &G.arcnum);
    for (int i = 0; i < G.arcnum; i++) {
        char v1, v2;
        scanf(" %c %c", &v1, &v2);
        int j = 0, k = 0;
        while (G.vexs[j] != v1) {
            j++;
        }
        while (G.vexs[k] != v2) {
            k++;
        }
        G.arc[j][k] = G.arc[k][j] = 1;
    }
    CreateTree(&G);
    return 0;
}

输入样例：

8
A B C D E F G H
8
A B
A C
B D
B E
C F
C G
F G
D H

输出样例：

A,B
A,C
B,D
B,E
C,F
C,G
D,H