文章目录
前言
一、树与图的广度优先遍历
二、AcWing 847. 图中点的层次
本题解析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：树与图的广度优先遍历，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、树与图的广度优先遍历
最短距离的题目可以使用广度优先遍历（bfs）去解决
二、AcWing 847. 图中点的层次
本题链接：AcWing 847. 图中点的层次
本博客提供本题截图：
本题解析
bfs的板子题，具体bfs的原理见：BFS，这里注意一下数组d在本题中不止起到了记录距离的作用，因为初始化为-1且距离必然是非负数的原因，数组d在这里同时起到了判重的作用
AC代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> using namespace std; const int N = 100010; int n, m; int h[N], e[N], ne[N], idx; int d[N]; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } int bfs() { memset(d, -1, sizeof d); queue<int> q; d[1] = 0; q.push(1); while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = d[t] + 1; q.push(j); } } } return d[n]; } int main() { scanf("%d%d", &n, &m); memset(h, -1, sizeof h); for (int i = 0; i < m; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b); } cout << bfs() << endl; return 0; }
三、时间复杂度
关于树与图的广度优先遍历的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
