You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
52 lines
906 B
52 lines
906 B
#include<iostream> //广度优先遍历
|
|
|
|
int main() {
|
|
int i,j,n,m, a, b, cur,book[101]= {0},e[101][101];
|
|
int que[10001],head,tail;
|
|
scanf("%d %d",&n,&m);
|
|
|
|
//初始化二维矩阵
|
|
for (i = 1; i <= m; ++i) {
|
|
for (int j = 1; j <= n; ++j) {
|
|
if (i == j)
|
|
e[i][j] = 0;
|
|
else
|
|
e[i][j] = 99999999; //假设99999999为正无穷
|
|
}
|
|
}
|
|
//读入顶点之间的边
|
|
for (i = 1; i <= m; ++i) { //读入顶点间的边
|
|
scanf("%d %d",&a,&b);
|
|
e[a][b] = 1;
|
|
e[b][a] = 1; //因为是无向图
|
|
}
|
|
//队列初始化
|
|
head=1;
|
|
tail=1;
|
|
//从1号顶点出发,将1号顶点加入队列
|
|
que[tail]=1;
|
|
tail++;
|
|
book[1]=1;
|
|
//当队列不为空的时候循环
|
|
while (head<tail && tail<=n) {
|
|
cur=que[head];
|
|
for (i = 1; i <= n; ++i) {
|
|
if (e[cur][i] == 1 && book[i] == 0) {
|
|
que[tail]=i;
|
|
tail++;
|
|
book[i] = 1;
|
|
}
|
|
if(tail>n) {
|
|
break;
|
|
}
|
|
}
|
|
head++;
|
|
}
|
|
for(i=1;i<tail;i++)
|
|
printf("%d",que[i]);
|
|
getchar();
|
|
getchar();
|
|
return 0;
|
|
}
|
|
|