1688: 图-无向连通图的广度优先遍历
金币值：2
定数：10
时间限制：1.000 s
内存限制：128 M
正确：10
提交：33
正确率：30.30% 命题人：
题目描述
建立一个无向连通图的邻接矩阵（顶点中存储的信息为顶点编号），然后给出广度优先搜索该图得到的序列（设图中顶点从1开始编号，从编号为1的顶点开始广度优先搜索）。
#include <stdio.h>
#define MAXVEX 100 /* 最大顶点数由用户定义 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct {
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX]; //0号单元不用
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开始）的顶点之间有一条边
第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