图的 BFS/DFS

C 里用二维数组存图:adj[u] 这一行装 u 的所有邻居,deg[u] 记 u 现在有几个邻居,加边就是 adj[u][deg[u]++] = v。无向图一条边要写两次:adj[u] 加 v、adj[v] 也要加 u,否则只能单向走。存好图,遍历才有的放矢。

队列就是一个数组加两个下标:q[tail++] 入队、q[head++] 出队、head == tail 即空。流程:起点入队并标 visited,循环 while (head < tail) 取队首,把它没访问过的邻居逐个入队并标记。先入队的先处理(先进先出),所以访问是一圈一圈由近到远扩散——示例图从 0 出发的 BFS 序是 0 1 2 3 4 5。每点最多入队一次,q 开 N 个格子刚好够。

DFS 是不撞墙不回头:访问 u、标记、对每个没访问的邻居递归 dfs(v)。函数调用本身就是栈,邻居走完自动出栈回溯,退回到还没走完的上一层继续钻——同一张图的 DFS 序是 0 1 3 2 4 5。两种遍历时间都是 O(V + E)、空间 O(V);跑完一种再跑另一种,记得 memset 清空 visited。