USTC机试—根据文件中的顶点对信息,输出广度优先遍历的结点序列
代码如下
#include<stdio.h>
#include<string>
#include<queue>
#define N 100
using namespace std;
queue<int> Edge[N];//定义以Edge[i](i是顶点开始)的邻接表信息
bool visit[N];
int main(){
FILE *fp1,*fp2;
int a,b;//保存顶点对信息
int n;
fp1=fopen("3.in","r");
fp2=fopen("3.out","w");
fscanf(fp1,"%d",&n);
while(!feof(fp1)){//只要读的文件没到结尾
fscanf(fp1,"%d %d\n",&a,&b);
Edge[a].push(b);//相邻结点信息压入其中
Edge[b].push(a);//无向图双方都要更新信息
}
for(int i=1;i<=n;i++){
visit[i]=false;//初始化都没访问
}
for(i=1;i<=n;i++){
if(visit[i]==false){//从结点1开始没访问就输出到文件中
fprintf(fp2,"%d ",i);
visit[i]=true;}//同时设置该点已经访问
while(!Edge[i].empty()){
int temp=Edge[i].front();//取出一个结点
Edge[i].pop();
if(visit[temp]==false){
fprintf(fp2,"%d ",temp);
visit[temp]=true;
}
}
}
return 0;
}