图上的遍历算法
广度优先搜索 BFS
概念
广度优先搜索（Breadth-First Search）是一种图遍历算法，用于在图或树中按层次逐层访问节点。它从源节点（起始节点）开始，首先访问源节点的所有直接邻接节点，然后依次访问距离源节点较远的节点，直到遍历完整个图或到达目标节点
BFS通过队列逐层扩展的方式，确保按最短路径访问节点，并且保证在无权图中找到从源节点到目标节点的最短路径，适用于寻找最短路径、连通分量和解决图的层次遍历等问题
时间复杂度：(O(V+E))，其中(V)是图中节点数（顶点数），(E)是图中的边数
实现方法
BFS 采用 队列（Queue） 来保证节点的逐层访问。每当一个节点被访问时，其所有未访问的邻接节点都会被加入队列，确保接下来的节点按照它们的距离起始节点的层数顺序依次访问
//伪代码 BFS(graph, start): 将起始节点 start 加入队列 queue 并标记为已访问 while queue 非空: 当前节点 node = 从队列中弹出 访问节点 node 遍历 node 的所有邻接节点 neighbor: if neighbor 没有被访问过: 标记 neighbor 为已访问 将 neighbor 加入队列 //C++代码（邻接表，维护了距离数组和前驱节点数组） //Q 队列，用于存储待访问的节点 //vis 访问标记数组，记录每个节点是否被访问过 //d 距离数组，记录每个节点从起始节点的最短距离 //p 前驱节点数组，记录每个节点的前驱节点，帮助恢复路径 //head[u] 节点u的邻接表的头节点 //e[i].to 边i的目标节点 //e[i].nxt 边i的下一个边的指针，用于遍历邻接表 void bfs(int u) { while (!Q.empty()) Q.pop();//清空队列 Q.push(u); vis[u] = 1; d[u] = 0; p[u] = -1; while (!Q.empty()) { u = Q.front(); Q.pop(); for (int i = head[u]; i; i = e[i].nxt) { if (!vis[e[i].to]) { Q.push(e[i].to); vis[e[i].to] = 1; d[e[i].to] = d[u] + 1; p[e[i].to] = u; } } } } void restore(int x) { vector<int> res; for (int v = x; v != -1; v = p[v]) res.push_back(v); reverse(res.begin(), res.end()); for (int i = 0; i < res.size(); ++i) printf("%d ", res[i]); } 层序遍历
例题 Leetcode 102 二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 （即逐层地，从左到右访问所有节点）
样例输入：
root = [3,9,20,null,null,15,7] 样例输出：
[[3],[9,20],[15,7]] 关键代码：
vector<vector<int>> levelOrder(TreeNode* root) { vector <vector <int>> ans; if (!root) return ans; queue <TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size();//队列中元素数量 ans.push_back(vector <int> ()); for (int i = 1; i <= size; ++i) { auto node = q.front(); q.pop(); ans.back().push_back(node->val); if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } return ans; } 最短路径
创建一个数组或字典来记录每个节点的最短路径（即距离）。初始时，将起点的距离设置为0，其他节点设置为 -1表示未被访问。广度优先搜索时，对于每个邻居节点，如果它尚未被访问过，则更新其最短路径为当前节点的最短路径+1，并将该邻居节点加入队列
例题 Luogu P1443 马的遍历
有一个 (n times m) 的棋盘，在某个点 ((x, y)) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步
输入：输入只有一行四个整数，分别为 (n, m, x, y)
输出：一个 (n times m) 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 (-1)）
样例输入：
3 3 1 1 样例输出：
0 3 2 3 -1 1 2 1 4 关键代码：
int vis[N][N],f[N][N]; int dx[8]={-1,-2,-2,-1,1,2,2,1}; int dy[8]={2,1,-1,-2,2,1,-1,-2};//8个方向 f[x][y]=0;//记录步数 q.push(make_pair(x,y)); vis[x][y]=true; while(!q.empty()) { int xx=q.front().first,yy=q.front().second; q.pop(); for(int i=0;i<8;i++) { int u=xx+dx[i],v=yy+dy[i]; if(u<1||u>n||v<1||v>m||vis[u][v])continue; vis[u][v]=true;q.push(make_pair(u,v)); f[u][v]=f[xx][yy]+1; } } Luogu B3625 迷宫寻路
迷宫可以视为一个 (ntimes m) 矩阵，每个位置要么是空地，要么是墙。机器猫初始时位于 ((1, 1)) 的位置，只能从一个空地走到其上、下、左、右的空地，问能否走到 ((n, m)) 位置
输入：第一行，两个正整数 (n,m)。 接下来 (n) 行，输入这个迷宫。每行输入一个长为 (m) 的字符串，# 表示墙，. 表示空地
输出：仅一行，一个字符串。如果机器猫能走到 ((n, m))，则输出 Yes；否则输出 No
样例输入：
3 5 .##.# .#... ...#. 样例输出：
Yes Luogu P1135 奇怪的电梯
大楼的每一层楼都可以停电梯，而且第 (i) 层楼（(1 le i le N)）上有一个数字 (K_i)（(0 le K_i le N)）。电梯只有四个按钮：开，关，上，下。上下的层数等于当前楼层上的那个数字。当然，如果不能满足要求，相应的按钮就会失灵。例如： (3, 3, 1, 2, 5) 代表了 (K_i)（(K_1=3)，(K_2=3)，……），从 (1) 楼开始。在 (1) 楼，按“上”可以到 (4) 楼，按“下”是不起作用的，因为没有 (-2) 楼。那么，从 (A) 楼到 (B) 楼至少要按几次按钮呢？
输入： 第一行为三个用空格隔开的正整数，表示 (N, A, B)（(1 le N le 200)，(1 le A, B le N)）。第二行为 (N) 个用空格隔开的非负整数，表示 (K_i)
输出：一行，即最少按键次数，若无法到达，则输出 -1
样例输入：
5 1 5 3 3 1 2 5 样例输出：
3 连通分量问题
无向图中的连通分量：是指图中所有节点都彼此连通的最大子集。对于一个无向图，如果你从一个节点出发，通过图中的边能访问到其他所有节点，那么这些节点组成一个连通分量。如果图的某个子集内的节点之间有路径相连，则该子集为一个连通分量
例题 Leetcode 200 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成
此外，你可以假设该网格的四条边均被水包围
样例输入：
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] 样例输出：
3 关键代码：
int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; //四个方向 void bfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) { queue<pair<int, int>> que; que.push({x, y}); visited[x][y] = true; while(!que.empty()) { pair<int ,int> cur = que.front(); que.pop(); int curx = cur.first; int cury = cur.second; for (int i = 0; i < 4; i++) { int nextx = curx + dir[i][0]; int nexty = cury + dir[i][1]; if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { que.push({nextx, nexty}); visited[nextx][nexty] = true; } } } } 深度优先搜索 DFS
概念
深度优先搜索（Depth-First Search）是一种用于图或树的遍历算法，它的基本思想是：从一个起始节点出发，沿着一条路径一直向下遍历，直到不能继续为止，然后回溯到上一个节点，继续探索其它未被访问的节点，直到所有节点都被访问过为止
DFS的核心思想是尽量深入每一个分支，探索到没有可再走的路径后，再回退到上一层节点进行其他路径的搜索
时间复杂度：(O(V+E))
实现方法
递归
实现DFS最常见的方法，能直观的利用函数调用栈自动进行回溯。递归地访问当前节点的所有未访问的邻居；每次递归调用都会进入下一个节点，直到无法访问为止，再回溯到上一个节点，继续访问其他未被访问的邻居
int n,path[N]; bool st[N + 1]; // 标记数组 void dfs(int u) // 排列第 u 个数 { if (u == n) { for (int i = 0; i < n; i++) printf("%5d", path[i]); printf("n"); return; } for (int i = 1; i <= n; i++) { if (!st[i]) { path[u] = i; // 将 i 放入当前排列的位置 st[i] = true; // 标记 i 已被使用 dfs(u + 1); // 递归 构造排列的下一个位置 st[i] = false; // 回溯 撤销选择，取消对 i 的标记 } } } 栈
显式地使用栈来模拟递归过程。从栈顶取出节点并访问，将当前节点的所有未访问的邻居压入栈中；当所有邻居被访问后，出栈，回溯到上一个节点。显式栈避免了递归带来的栈溢出问题，适合于需要较大深度遍历的场景
vector<vector<int>> adj; //邻接表 vector<bool> vis; //记录节点是否已经遍历 void dfs(int s) { stack<int> st; st.push(s); vis[s] = true; while (!st.empty()) { int u = st.top(); st.pop(); for (int v : adj[u]) { if (!vis[v]) { vis[v] = true; //确保栈里没有重复元素 st.push(v); } } } } 回溯问题
当递归到某一层时，如果发现当前状态不符合条件，或者已经找到一个解，就撤销当前的操作，返回到上一个状态，继续尝试其他的选择
例题 Acwing 843 N皇后问题
将 (n) 个皇后放在 (n times n) 的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输出所有的满足条件的棋子摆法
输入：共一行，包含整数 (n)
输出：每个解决方案占 (n) 行，每行输出一个长度为 (n) 的字符串，用来表示完整的棋盘状态。其中 ”(.)” 表示某一个位置的方格状态为空，”(Q)” 表示某一个位置的方格上摆着皇后。每个方案输出完成后，输出一个空行
输入样例：
4 输出样例：
.Q.. ...Q Q... ..Q. ..Q. Q... ...Q .Q.. 关键代码：
int n; char g[N][N];//用来存路径 bool col[N], dg[N], udg[N];//col列，dg对角线，udg反对角线，用来判断该位置是否可行 void dfs(int u) { if (u == n) { for (int i = 0; i < n; i ++ ) puts(g[i]); puts(""); return; } int x = u; for (int y = 0; y < n; y ++ ) if (col[y] == false && dg[y - x + n] == false && udg[y + x] == false) { col[y] = dg[y - x + n] = udg[y + x] = true; g[x][y] = 'Q'; dfs(x + 1); g[x][y] = '.'; col[y] = dg[y - x + n] = udg[y + x] = false; } } Luogu P1706 全排列问题
按照字典序输出自然数 (1) 到 (n) 所有不重复的排列，即 (n) 的全排列，要求所产生的任一数字序列中不允许出现重复的数字
输入：一个整数 (n)
输出：由 (1 sim n) 组成的所有不重复的数字序列，每行一个序列。每个数字保留 (5) 个场宽
样例输入：
3 样例输出：
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 强连通分量
在有向图 (G) 中，如果两个顶点 (u) ，(v) 间有一条从 (u) 到 (v) 的有向路径，同时还有一条从 (v) 到 (u) 的有向路径，则称两个顶点强连通。如果有向图 (G) 的每两个顶点都强连通，称 (G) 是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量
如上图，({1,2,3,5})为一个强连通分量，因为顶点 (1,2,3,5) 两两可达
Tarjan算法
- 从每个未访问的节点开始执行DFS。在DFS的过程中，记录节点的发现时间
DFN，更新最早可到达的祖先节点LOW - 当某个节点的
LOW值等于其发现时间DFN时，说明从该节点开始的节点（包括它本身）形成了一个强连通分量。此时，从栈中弹出所有节点，并将它们标记为同一强连通分量 - 栈
stack在算法中用于保存当前DFS路径中的节点，直到识别到一个强连通分量时，再从栈中弹出这些节点
//vis[] 用于标记节点是否在栈中，避免重复处理 //stack[] 栈，用于存放当前DFS访问路径上的节点 //LOW[] 表示节点pos能回到的最早节点的时间戳 //DFN[] 记录节点的DFS发现时间 //dfs_num DFS的计数器，用于给每个节点标记一个唯一的访问时间戳 //size[] 记录每个强连通分量的大小 //dye[] 标记每个节点属于哪个强连通分量 //CN 当前强连通分量的编号 //pre[]和E[] 用于存储图的边和邻接表，pre[pos]存储pos节点的出边 void tarjan(int pos){ vis[stack[++index]=pos]=1;//入栈并标记 LOW[pos]=DFN[pos]=++dfs_num; for(int i=pre[pos];i;i=E[i].next){ if(!DFN[E[i].to]){ tarjan(E[i].to); LOW[pos]=min(LOW[pos],LOW[E[i].to]); } else if(vis[E[i].to]) LOW[pos]=min(LOW[pos],DFN[E[i].to]); } if(LOW[pos]==DFN[pos]){ vis[pos]=0; size[dye[pos]=++CN]++;//染色及记录强连通分量大小 while(pos!=stack[index]){ vis[stack[index]]=0; size[CN]++;//记录大小 dye[stack[index--]]=CN;//弹栈并染色 } index--; } } 例题 Luogu P2341 受欢迎的牛
被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 (A) 喜欢 (B)，(B) 喜欢 (C)，那么 (A) 也喜欢 (C)。牛栏里共有 (N) 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星
输入：第一行是两个用空格分开的整数 (N) 和 (M)；接下来 (M) 行是每行两个用空格分开的整数 (A) 和 (B)，表示 (A) 喜欢 (B)
输出：一行单独一个整数，表示明星奶牛的数量
样例输入：
3 3 1 2 2 1 2 3 样例输出：
1 关键代码：
void tarjan(int u) { low[u]=dfn[u]=++dfn_sum; stack[top++]=u; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dfn(v)) low[u]=min(low[u],dfn[v]); else { tarjan(v); low[u]=min(low[u],low[v]); } } if(low[u]==dfn[u]) { int now=stack[--top];s_sum++; s[u]+=s_sum; while(now!=u) { s[now]=s_num; now=s[--top]; } } } 拓扑排序
对于图中的每条有向边 (u to v)，在排序结果中，顶点 (u) 必须排在顶点 (v) 的前面
只适用于有向无环图，也叫拓扑图
该图拓扑序列为 (ABDC) 或 (ADBC)
Kahn算法
入度：多少条边指向该节点，入度为 0 的点可以排在最前位置
出度：该节点指向多少条边
先计算每个节点的入度，选择所有入度为 0 的节点作为初始节点，加入结果列表。移除这些节点及其出度边，更新相邻节点的入度。如果有相邻节点的入度变为 0，则继续加入队列，直到所有节点都被处理完
//伪代码 queue <- 所有入度为 0 的点 while queue 不空 { t <- 队头 枚举 t 的所有出边 t->j 删掉t->j,d[j]--; } 例题 Luogu B3644 拓扑排序
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出
输入：第 (1) 行一个整数 (N)，表示家族的人数。接下来 (N) 行，第 (i) 行描述第 (i) 个人的后代编号 (a_{i,j})，表示 (a_{i,j}) 是 (i) 的后代。每行最后是 (0) 表示描述完毕
输出：输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可
样例输入：
5 0 4 5 1 0 1 0 5 3 0 3 0 样例输出：
2 4 5 3 1 关键代码：
queue <int> Q; void toposort() { for(int i = 1; i <= n; i++) { if(deg[i] == 0) { printf("%d ", i); Q.push(i); } } while(Q.size()) { int x = Q.front(); Q.pop(); for(int i = Head[x]; i; i = Next[i]) { deg[to[i]]--; if(deg[to[i]] == 0) { printf("%d ", to[i]); Q.push(to[i]); } } } } 环的检测
环指在图中从某个顶点出发，沿着图的有向边/无向边遍历后能够回到该顶点的路径
拓扑排序适用于有向无环图。如果一个有向图可以进行拓扑排序，则说明该图没有环。如果不能进行拓扑排序，说明图中存在环
例题 Leetcode 207 课程表
你这个学期必须选修 numCourses 门课程
在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi]，表示如果要学习课程 ai 则必须先学习课程 bi
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false
样例输入：
numCourses = 2, prerequisites = [[1,0],[0,1]] 样例输出：
false 关键代码：
bool toposort() { int hh = 0, tt = -1; for (int i = 1; i <= n; i ++ ) if (!d[i]) q[ ++ tt] = i; while (hh <= tt) { int t = q[hh ++ ]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (-- d[j] == 0) q[ ++ tt] = j; } } return tt == n - 1; } 
