题目描述
给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始
以下代码框架仅供参考，同学们可在理解的基础上自行设计算法，不强制要求和框架相同
注意：图n个顶点编号从0到n-1
代码框架如下：
输入
第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开
输入样例1
2 4 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 0 5 0 0 0 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0
输出样例1
0 2 3 1 0 3 4 2 1
思路分析
它的代码框架我们就不看了，文字太多，不想看，不过是个BFS，我们自己写。
毫无疑问我们需要用到队列，这次不用自己写一个队列了，没说不能用STL吧。
把队首元素取出来，标记为已访问，之后把队首元素连接的节点入队，重复操作，直到队列为空，这不就完事了。
当然，为了避免它是一个非连通的图，我们需要遍历每一个未曾访问的节点去BFS，具体看代码就懂了，代码这么短。
AC代码
代码语言：javascript复制#include<iostream>
#include<queue>
using namespace std;
const int max_vertex_number=20;
class Map{
int vertex_number=0;
bool visited[max_vertex_number]={false};
int matrix[max_vertex_number][max_vertex_number];
public:
Map(){
cin>>vertex_number;
for(int i=0;i<vertex_number;i )
for(int j=0;j<vertex_number;j )
cin>>matrix[i][j];
}
void BFS(int cur){
queue<int>open;
open.push(cur);
cout<<cur<<' ';
visited[cur]= true;
while(!open.empty()){
cur=open.front();
open.pop();
for(int i=0;i<vertex_number;i )
if(matrix[cur][i]&&visited[i]== false){
cout<<i<<' ';
visited[i]= true;
open.push(i);
}
}
}
void Traverse(){
for(int i=0;i<vertex_number;i )
if(visited[i]== false)
BFS(i);
cout<<endl;
}
};
int main() {
int t;
cin>>t;
while(t--){
Map test;
test.Traverse();
}
return 0;
}
