- 正确答案：DFS（Depth-First Search，深度优先搜索）是一种用于遍历或搜索图或树的算法。它从起始节点开始，沿着一条路径尽可能深入地访问未访问过的相邻节点，直到无法继续前进（即到达叶子节点或没有未访问的邻接点），然后回溯到上一个节点，继续探索其他分支。该过程重复直至所有可达节点都被访问。 - 解答思路： 1. 明确DFS的基本行为：优先“向下”探索，而不是“横向”扩展。 2. 理解其递归本质：每次访问一个节点后，立即递归处理其未访问的邻居。 3. 考虑实现方式：可以使用系统栈（递归）或手动维护栈（迭代）来实现。 4. 注意标记已访问节点，防止重复访问造成死循环，尤其是在图结构中存在环的情况下。 5. 根据具体问题决定是否需要记录路径、层级、状态等信息。 - 深度知识讲解： DFS的核心思想是“回溯 + 探索”，属于盲目搜索策略之一，常用于解决连通性、路径存在性、拓扑排序、强连通分量、岛屿数量、排列组合生成等问题。数据结构基础： - 图通常用邻接表或邻接矩阵表示。 - 邻接表：适合稀疏图，空间复杂度O(V + E)，常用vector>或unordered_map>存储。 - 访问标记一般使用布尔数组visited[]或集合set来记录已访问节点。时间与空间复杂度： - 时间复杂度：O(V + E)，其中V是顶点数，E是边数。每个节点和每条边最多被访问一次。 - 空间复杂度：O(V)，主要来自递归调用栈或显式栈的深度，最坏情况下为O(V)，例如链状图。实现原理对比： - 递归实现：简洁直观，利用函数调用栈自动保存路径状态。 - 迭代实现：使用显式栈stack>模拟递归过程，适用于需要控制状态或避免栈溢出的场景。应用场景扩展： - 在树中：前序、中序、后序遍历本质上都是DFS的不同形式。 - 在无向图中：可用于检测环（若遇到已访问的非父节点，则有环）。 - 在有向图中：可用于拓扑排序（结合入度或后序逆序）、判断环路（三色标记法：白-未访问，灰-正在访问，黑-已完成）。 - 回溯算法（Backtracking）是DFS的一种特例，常用于求解组合、排列、N皇后、数独等问题，强调“尝试-失败-恢复”机制。与BFS对比： - BFS使用队列，按层扩展，适合求最短路径（无权图）。 - DFS使用栈，适合路径构造、连通分量分析、状态空间探索。 - 伪代码（递归版，适用于无向图）： ``` function dfs(graph, node, visited) if node is in visited return add node to visited print node // 或执行其他操作 for each neighbor in graph[node] dfs(graph, neighbor, visited) // 主调用 visited = empty set dfs(graph, start_node, visited) ``` - 伪代码（迭代版）： ``` function dfs_iterative(graph, start) stack = empty stack visited = empty set push start onto stack while stack is not empty node = pop from stack if node is not in visited add node to visited print node for each neighbor in reverse order of graph[node] // 保证顺序一致 if neighbor not in visited push neighbor onto stack ``` 注：迭代版本中，将邻接点逆序压栈是为了使下一个被处理的节点与递归版本保持一致（因栈是后进先出）。 - 扩展知识点： 1. 三色标记法（Three-color labeling）： - 白色：未访问。 - 灰色：正在访问其子节点（在递归栈中）。 - 黑色：已完成所有子节点访问。可用于检测有向图中的环：若在DFS过程中发现一条边指向灰色节点，则存在环。 2. DFS树与边分类（有向图）： - 树边（Tree Edge）：构成DFS生成树的边。 - 回边（Back Edge）：指向祖先节点的边 → 表示环。 - 前向边（Forward Edge）：指向后代但非直接子节点。 - 交叉边（Cross Edge）：连接不同子树的边。其中，回边的存在是有向图含环的充要条件。 3. 时间戳机制：在DFS过程中维护两个时间戳：discovery_time 和 finish_time。可用于判断祖先关系、进行拓扑排序、识别强连通分量（Tarjan算法）等。 - 示例代码（C++风格，邻接表+递归DFS）： ``` #include #include #include using namespace std; void dfs(const vector>& graph, int node, unordered_set& visited) { visited.insert(node); cout << node << " "; for (int neighbor : graph[node]) { if (visited.find(neighbor) == visited.end()) { dfs(graph, neighbor, visited); } } } int main() { int n = 5; vector> graph(n); // 添加边：0-1, 0-2, 1-3, 2-4 graph[0] = {1, 2}; graph[1] = {3}; graph[2] = {4}; unordered_set visited; dfs(graph, 0, visited); return 0; } ``` 输出：0 1 3 2 4 总结：掌握DFS不仅要理解其基本流程，更要熟悉其在不同数据结构中的实现方式、常见变体（如带状态回溯）、以及与其他算法（如回溯、Tarjan、拓扑排序）的关系。它是算法面试中最基础也最重要的图论工具之一。

饿了么java技术面经

全站热榜

创作者周榜