图 图的遍历
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了图 图的遍历,现在分享给大家,供学习和参考。文章包含1271字,纯文字阅读大概需要4分钟。
教程信息
对于同一张图,可能会产生不同的遍历序列,因为图并没有一个确定的起点。
1、深度优先遍历:
访问该节点,然后依次访问与该节点相邻的未被访问的节点,直到所有相邻节点都被访问
如下图以v1开始的一个深度优先遍历结果是V1 -> V2 -> V4 -> V8 -> V5 -> V3 -> V6 -> V7
深度优先遍历使用递归实现
2、广度优先遍历:
访问该节点,然后依次访问该节点的所有相邻节点,直到所有节点都被访问为止
如下图以v1开始的一个广度优先遍历结果是V1 -> V2 -> v3 -> V4 -> V5 -> V6 -> V7 -> V8
广度优先遍历使用队列实现
通过题目解题认识图的遍历
题目来源:
https://www.luogu.com.cn/problem/P5318
题目内容:
实现代码:
#include<bits/stdc++.h> using namespace std; const int MAXN = 1000005; int n, m; vector < int > p[MAXN]; //邻接表 int VIS[MAXN]; //搜索审查数组 void dfs(int x) { cout << x << ' '; for (int i = 0; i < p[x].size(); i++) if (VIS[p[x][i]] == 0) { VIS[p[x][i]] = 1; dfs(p[x][i]); } } void bfs(int x) { queue < int > q; q.push(1); VIS[1] = 1; while (q.empty() == false) { int x = q.front(); q.pop(); cout << x << " "; for (int i = 0; i < p[x].size(); i++) if (VIS[p[x][i]] == 0) { VIS[p[x][i]] = 1; q.push(p[x][i]); } } } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; p[x].push_back(y); //x为顶点的边<x,y>,无边权 } for (int i = 1; i <= m; i++) sort(p[i].begin(), p[i].end()); VIS[1] = 1; dfs(1); cout << endl; memset(VIS, 0, sizeof VIS); bfs(1); }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供图 图的遍历的全部内容,希望教程文章能够帮你了解学习图 图的遍历,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-299.html