建立一个无向连通图的邻接矩阵（顶点中存储的信息为顶点编号），然后给出广度优先搜索该图得到的序列（设图中顶点从1开始编号，从编号为1的顶点开始广度优先搜索）。 #include <stdio.h> #define MAXVEX 100 /* 最大顶点数由用户定义 */ typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ typedef struct { VertexType vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numNodes; int numEdges; } AMGraph; int visited[MAXVEX]; //设置一个全局数组表示图中的顶点是否已经访问过，0号单元不表示有效数字 void BFS(AMGraph G, int v); void CreateGraph(AMGraph &G) { /*该函数平台已提供*/ } int main(void) { AMGraph G; scanf("%d %d",&G.numNodes,&G.numEdges); CreateGraph(G); BFS(G,1); // 从编号为1的顶点开始进行广度优先搜索 return 0; } /*仅提供以下代码*/ void BFS(AMGraph G, int v) { } 输入 第1行输入两个整数，分别表示图中的顶点数n和边数m 第2-m+1行每行输入两个整数i和j，分别表示编号为i的顶点和编号为j（编号从1开始）的顶点之间有一条边 输出 共1行信息有n个整数，表示广度优先搜索该图得到的序列，序列之间用一个空格隔开 样例输入 复制 8 9 1 2 1 3 2 4 2 5 3 6 3 7 4 8 5 8 6 7 样例输出 复制 1 2 3 4 5 6 7 8

下面是完整的代码实现：

#include <stdio.h>
#include <queue>
#define MAXVEX 100

typedef char VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numNodes;
    int numEdges;
} AMGraph;

int visited[MAXVEX];

void BFS(AMGraph G, int v);

void CreateGraph(AMGraph &G) {
    int i, j, k;
    scanf("%d%d", &G.numNodes, &G.numEdges);
    for (i = 0; i < G.numNodes; i++) {
        scanf("%d", &G.vexs[i]);
    }
    for (i = 0; i < G.numNodes; i++) {
        for (j = 0; j < G.numNodes; j++) {
            G.arc[i][j] = 0;
        }
    }
    for (k = 0; k < G.numEdges; k++) {
        scanf("%d%d", &i, &j);
        G.arc[i - 1][j - 1] = 1; // 有向图
        G.arc[j - 1][i - 1] = 1; // 无向图
    }
}

int main(void) {
    AMGraph G;
    CreateGraph(G);
    BFS(G, 0); // 从编号为1的顶点开始进行广度优先搜索
    return 0;
}

void BFS(AMGraph G, int v) {
    int i;
    std::queue<int> Q;
    Q.push(v);
    visited[v] = 1;
    while (!Q.empty()) {
        int w = Q.front();
        printf("%d ", G.vexs[w]);
        Q.pop();
        for (i = 0; i < G.numNodes; i++) {
            if (G.arc[w][i] == 1 && visited[i] == 0) {
                Q.push(i);
                visited[i] = 1;
            }
        }
    }
}

注意，这里使用的是无向图，因此在创建图的时候需要把两个方向都连上，即：

G.arc[i - 1][j - 1] = 1; // 有向图
G.arc[j - 1][i - 1] = 1; // 无向图

最后输出的是顶点的编号，因此在 BFS 函数中要输出 `G.vexs[w]`。