asp.net网站打不开html页面,天华集团设计公司,软件技术招聘信息,电脑做系统哪个网站比较好用题目描述 广度优先搜索遍历类似于树的按层次遍历的过程。其过程为#xff1a;假设从图中的某顶点v出发#xff0c;在访问了v之后依次访问v的各个未曾被访问过的邻接点#xff0c;然后分别从这些邻接点出发依次访问它们的邻接点#xff0c;并使“先被访问的顶点的邻接点”先… 题目描述 广度优先搜索遍历类似于树的按层次遍历的过程。其过程为假设从图中的某顶点v出发在访问了v之后依次访问v的各个未曾被访问过的邻接点然后分别从这些邻接点出发依次访问它们的邻接点并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问则另选图中一个未曾被访问的顶点作为起始点。重复上述过程直至图中所有顶点都被访问到为止。 其算法可以描述如下 在本题中读入一个无向图的邻接矩阵即数组表示建立无向图并按照以上描述中的算法遍历所有顶点输出遍历顶点的顺序。 输入 输入的第一行包含一个正整数n表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1对于第i行的第j个0或11表示第i个顶点和第j个顶点有直接连接0表示没有直接连接。当i和j相等的时候保证对应的整数为0。 输入保证邻接矩阵为对称矩阵即输入的图一定是无向图。 输出 只有一行包含n个整数表示按照题目描述中的广度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格并请注意行尾输出换行。 样例输入 复制 4 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 样例输出 复制 0 3 1 2 提示 在本题中需要熟练掌握图的邻接矩阵存储方式。在建立完成无向图之后需要严格按照题目描述的遍历顺序对图进行遍历。另外算法中描述的FirstAdjVex函数和NextAdjVex函数需要认真的自行探索并完成。在本题中需要使用队列结构需要对队列的概念进行复习。 通过这道题目应该能够对图的广度优先搜索建立更加直观和清晰的概念. 题解 t tii #includebits/stdc.h
using namespace std;
using ll long long;const int N 105;int mp[N][N];int n;bool vis[N];void dfs(int u){cout u ;vis[u] true;for(int i 0;i n;i ){if(mp[u][i] 1 !vis[i]){dfs(i);}}
}
void bfs(int u){queueintq;q.push(u);while(!q.empty()){int cu q.front();q.pop();cout cu ;vis[cu] true;for(int i 0;i n;i ){if(mp[cu][i] 1 !vis[i]){vis[i] true;q.push(i);} }}
}int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin n;for(int i 0;i n;i )for(int j 0;j n;j )cin mp[i][j];bfs(0);return 0;
}
