|
Time Limit: 1sec Memory Limit:256MB
Description
读入图的邻接矩阵以及一个顶点的编号（图中顶点的编号为从1开始的连续正整数。顶点在邻接矩阵的行和列上按编号递增的顺序排列。邻接矩阵中元素值为1，表示对应顶点间有一条边，元素值为0，表示对应顶点间没有边），输出从该顶点开始进行广度优先搜索（Breadth-First Search, BFS）的顶点访问序列。假设顶点数目<=100，并且，对于同一顶点的多个邻接顶点，按照顶点编号从小到大的顺序进行搜索。
Input
第一行为两个整数n和s (0<n<=100, 0<s<=100)，n表示图中顶点的数目，s为搜索的起始顶点的编号。
后面的n行表示图的邻接矩阵，每行为n个整数，相邻整数间用一个空格间隔。
Output
一行（行末没有换行符），表示从顶点s开始进行BFS的顶点访问序列，相邻顶点间用一个空格间隔。
Sample Input
4 3 Sample Output
3 1 2 4 |
#include<iostream>
#include<queue>
#include<memory>
using namespace std; const int MAX=1001;
int edge[MAX][MAX];
int n; //顶点数
bool isvisited[MAX];
queue<int>q;
queue<int>haha; void BFS()
{
if(!q.empty())
{
int a=q.front();
q.pop(); for(int i=1;i<=n;i++)
{
if(!isvisited[i]&&edge[a][i])
{
isvisited[i]=true;
haha.push(i);
q.push(i);
}
}
BFS();
}
} int main()
{
cin>>n; int start;
cin>>start;
q.push(start); memset(isvisited, false, sizeof(isvisited)); for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>edge[i][j]; isvisited[start]=true;
haha.push(start);
BFS();
while(haha.size()>1)
{
cout<<haha.front()<<" ";
haha.pop();
}
cout<<haha.front();
// cout<<endl; return 0;
}