图
深度优先搜索
深度优先搜索（DFS）的探索方式是：沿着一条路尽可能往深处走，走不动了再回头。这就像在纸上走迷宫：顺着一条走廊一直走到尽头，只有撞上死路时，才退回上一个岔口、换一个方向再试。DFS 会一条路走到底，然后回溯。
它天然的引擎是一个栈（后进先出）——而拿到一个栈最简单的办法就是递归，递归用的正是程序自己的调用栈。到达某顶点后先标记它已访问，然后递归进入它第一个未访问的邻居，再进入那个邻居第一个未访问的邻居，依此类推；当一个顶点再没有未访问的邻居时，递归就返回（回溯）到上一个顶点。和 BFS 一样，正是“标记已访问”阻止了环造成的无限循环。也可以用一个显式的 std::stack 把 DFS 写成迭代形式。
DFS 同样对每个顶点访问一次、对每条边检查一次，在邻接表上为 O(V + E) 时间。它不求最短路径，但这种“先把当前分支走完”的深入顺序，非常适合检测环、求连通分量、枚举所有方案，以及对有向无环图做拓扑排序等任务。
vector<bool> seen(n, false);
void dfs(int v) {
seen[v] = true; // visit v
for (int nb : adj[v])
if (!seen[nb]) dfs(nb); // dive deeper
} // return = backtrack每次调用都深入一个邻居；返回就是回溯的那一步。
在很深的图上，递归式 DFS 可能撑爆调用栈；改用显式栈可以避开这个限制。
又称
另见