邻接表建数或图
用 h 数组保存各个节点能到的第一个节点的编号。开始时，h[i] 全部为 -1。
用 e 数组保存节点编号，ne 数组保存 e 数组对应位置的下一个节点所在的索引。
用 idx 保存下一个 e 数组中，可以放入节点位置的索引
插入边使用的头插法，例如插入：a->b。首先把b节点存入e数组，e[idx] = b。然后 b 节点的后继是h[a]，ne[idx] = h[a]。最后，a 的后继更新为 b 节点的编号，h[a] = idx，索引指向下一个可以存储节点的位置，idx ++ 。
//邻接表
int h[N], e[N * 2], ne[N * 2], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}树或图的DFS
bool st[N];
// 需要标记数组st[N], 遍历节点的每个相邻的便
void dfs(int u) {
st[u] = true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
dfs(j);
}
}
}树或图的BFS
经典例题：图中点的层次
给定一个 n𝑛 个点 m𝑚 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 11，点的编号为 1∼n1∼𝑛。
请你求出 11 号点到 n𝑛 号点的最短距离，如果从 11 号点无法走到 n𝑛 号点，输出 −1−1。
输入格式
第一行包含两个整数 n𝑛 和 m𝑚。
接下来 m𝑚 行，每行包含两个整数 a𝑎 和 b𝑏，表示存在一条从 a𝑎 走到 b𝑏 的长度为 11 的边。
输出格式
输出一个整数，表示 11 号点到 n𝑛 号点的最短距离。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int h[N],ne[N], e[N], idx;//邻接表数据结构
int dist[N];//存储距离
int st[N];//标记点是否走到过
int n, m;
void add(int a, int b)//邻接表存储图
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs()
{
memset(dist, 0x3f, sizeof(dist));//初始都没有走到过，距离无穷大
dist[1] = 0;//从1号节点开始，距离为0
queue<int> q;//队列
q.push(1);//1号节点入队列
st[1] = 1;//1到1的距离为0，已经求出
while(q.size())//对列非空，就一直往后搜索
{
int t = q.front();//队头出队，找该点能到的点
q.pop();
for(int i = h[t]; i != -1; i = ne[i])//遍历所有t节点能到的点，i为节点索引
{
int j = e[i];//通过索引i得到t能到的节点编号
if(!st[j])//如果没有遍历过
{
dist[j] = dist[t] + 1;//距离为t号节点的距离+1
q.push(j);//节点入队
st[j] = 1;//入队后标记，已经遍历过了
}
}
}
}
int main()
{
cin >> n >>m;
memset(h, -1, sizeof h);//初始化，所有节点没有后继，后继都是-1
for(int i = 0; i < m; i++)//读入所有边
{
int a, b;
cin >> a >> b;
add(a, b);//加入邻接表
}
bfs();//广度优先遍历
cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]);//如果到n号节点的距离不是无穷大，输出距离，如果是无穷大，输出-1.
return 0;
}思路：
用 dist 数组保存1号节点到各个节点的距离，初始时，都是无穷大。
用 st 数组标记各个节点有没有走到过。
从 1 号节点开始，广度优先遍历：
1 号节点入队列，dist[1] 的值更新为 0。
如果队列非空，就取出队头，找到队头节点能到的所有节点。如果队头节点能到走到的节点没有标记过，就将节点的dist值更新为队头的dist值+1，然后入队。
重复步骤 2 直到队列为空。
这个时候，dist数组中就存储了 1 号节点到各个节点的距离了。如果距离是无穷大，则不能到达，输出 -1，如果距离不是无穷大，则能到达，输出距离。
评论区