图的按录入顺序广度优先搜索

5000(ms) 10000(kb) 2347 / 4868 Tags: 广度优先 图的广度优先搜索类似于树的按层次遍历，即从某个结点开始，先访问该结 点，然后访问该结点的所有邻接点，再依次访问各邻接点的邻接点。如此进 行下去，直到所有的结点都访问为止。在该题中，假定所有的结点以“A”--“Z ”中的若干字符表示，且要求结点的访问顺序根据录入的顺序进行访问。如果 结点录入的顺序为HUEAK，要求从H开始进行广度优先搜索，则可能的搜索 结果为：H->E->A->U->K.

输入

第一行为一个整数n，表示顶点的个数，第二行为n个大写字母构成的字符串，
表示顶点，接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为
0表示不邻接，否则为相应的边的长度。最后一行为一个字符，表示要求进行
广度优先搜索的起始顶点。

输出

用一行输出广度优先搜索结果，起始点为给定的顶点。

样例输入

5
HUEAK
0 0 2 3 0
0 0 0 7 4
2 0 0 0 0
3 7 0 0 1
0 4 0 1 0
H

样例输出

HEAUK

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<queue>
 5 using namespace std;  6 
 7 char Node[1000];  8 int Mark[1000]={0},Map[1000][1000],n;  9 queue<int> S; 10 
11 void bfs(int x){ 12  S.push(x); 13     while(!S.empty()){ 14         int tem=S.front(); 15         for(int i=0;i<n;i++){ 16             if(!Mark[i]&&Map[tem][i]){ 17  S.push(i); 18                 Mark[i]=1; 19  } 20  } 21         cout<<Node[tem]; S.pop(); 22  } 23 } 24 
25 int main() 26 { 27     char s; 28     cin>>n; 29     scanf("%s",Node); 30     for(int i=0;i<n;i++) 31         for(int j=0;j<n;j++) 32             cin>>Map[i][j]; 33     cin>>s; 34     int i=0; 35     while(Node[i]!=s)i++; 36     Mark[i]=1; 37  bfs(i); 38     return 0; 39 }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄