1397: 图的遍历——广度优先搜索

题目描述

广度优先搜索遍历类似于树的按层次遍历的过程。其过程为：假设从图中的某顶点v出发，在访问了v之后依次访问v的各个未曾被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点。重复上述过程，直至图中所有顶点都被访问到为止。

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。

输入

输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。

以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。

输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。

输出

只有一行，包含n个整数，表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。

样例输入

0 0 0 1
0 0 1 1
0 1 0 1
1 1 1 0

样例输出

0 3 1 2 

提示

在本题中，需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后，需要严格按照题目描述的遍历顺序对图进行遍历。在本题中需要使用队列结构，需要对队列的概念进行复习。

通过这道题目，应该能够对图的广度优先搜索建立更加直观和清晰的概念。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 55;
struct Graph{//邻接表存储 int vnum;//图中结点个数 vector<int>e[N];//行不可变，列可变的二维数组 
};
bool vis[N];//访问标记数组,用于标记已经访问过的结点void bfs(Graph &G,int x){//从图中结点x开始遍历 queue<int>q;//bfs需要有队列来辅助遍历q.push(x);vis[x]=1;//在入队的时候就要把当前访问的结点x标记为已访问while(q.empty()==false){//队列非空时，继续访问,等价写法while(!q.empty())int p = q.front();//p赋值为当前队列的队头结点的值 q.pop();//将队头结点出队printf("%d ",p); for(int i=0;i<G.e[p].size();++i){//扫描遍历p结点的所有邻接点，即队头结点的所有邻接点 if(vis[G.e[p][i]]==0){//如果当前结点没有被访问过，则入队并标记为已访问 q.push(G.e[p][i]);//在入队的时候就要把入队的结点标记为已访问，目的是为了防止后续结点有相同的邻接点时造成重复入队 vis[G.e[p][i]]=1;//G.e[p][i]表示邻接表G的第p行，第i列的结点，即p的第i个邻接点 }}}
} 
void bfsTravel(Graph &G){memset(vis,0,sizeof(vis));//初始化访问数组（如果有多组测试输入一定要初始化）for(int i=0;i<G.vnum;++i){if(!vis[i]){bfs(G,i);}}	 
}
int main(void){Graph G;scanf("%d",&G.vnum);//输入结点个数 for(int i=0;i<G.vnum;++i){for(int j=0;j<G.vnum;++j){int flag;scanf("%d",&flag);if(flag==1){//如果输入为1，则说明e[i][j]存在无向边 G.e[i].push_back(j);//在邻接表第i行后面加上一个j，表示i和j有边 //此操作相当于邻接矩阵输入直接转换成邻接表 }}}bfsTravel(G);return 0;
}