北京网站建设知名公司排名,教育网站制作哪个好,wordpress 内存不断上升,ai绘图网页版免费图的广度优先搜索 题目描述#xff1a; 图的广度优先搜索类似于树的按层次遍历#xff0c;即从某个结点开始#xff0c;先访问该结点#xff0c;然后访问该结点的所有邻接点#xff0c;再依次访问各邻接点的邻接点。如此进行下去#xff0c;直到所有的结点都访问为止。在… 图的广度优先搜索 题目描述 图的广度优先搜索类似于树的按层次遍历即从某个结点开始先访问该结点然后访问该结点的所有邻接点再依次访问各邻接点的邻接点。如此进行下去直到所有的结点都访问为止。在该题中假定所有的结点以“A”--“Z”中的若干字符表示且要求结点的访问顺序要求根据由“A”至“Z”的字典顺序进行访问。例如有如下图 如果要求从H开始进行广度优先搜索则搜索结果为H-A-E-K-U. 输入 输入只包含一个测试用例第一行为一个自然数n表示顶点的个数第二行为n个大写字母构成的字符串表示顶点接下来是为一个n*n大小的矩阵表示图的邻接关系。数字为0表示不邻接否则为相应的边的长度。 最后一行为一个字符表示要求进行广度优先搜索的起始顶点。 输出 用一行输出广度优先搜索结果起始点为给定的顶点各顶点之间用一个空格隔开。要求同一顶点的邻接点的访问顺序按“A”---“Z”的字典顺序。 输入样例 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 输出样例 H A E K U 代码
#includeiostream
#includecstdio
#includestring
#includecstring
#includestring.h
#includealgorithm
#includecmath
#includevector
#includequeue
#includestack
#includemap
using namespace std;
typedef pairint,int PII;
const int N 1e2 10;
int n;
string str;
int a[N][N];
int book[N];
int main(){ cin n;cin str;for(int i 0;i n;i )for(int j 0;j n;j )cin a[str[i] - A][str[j]-A];char c;cin c;queueint q;q.push(int(c-A));book[c - A] 1;cout c ;while(q.size()){auto t q.front();if(!book[t])cout (char)(t A) ;q.pop();book[t] 1;for(int i 0;i 26;i ){if(book[i] 0 a[t][i] ! 0){q.push(i); }}}return 0;
}
