算法阅读笔记

Graph Depth-First Search

DFS explores one path as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.

类型算法分类Graphs深度初级典型复杂度O(V+E)

简短面试回答

先从这个心智模型开始

DFS explores one path as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.

简单解释

它如何工作，不堆砌不必要的术语

Mark a node visited before exploring neighbors to avoid cycles.

Across a graph represented by adjacency lists, traversal is O(V + E).

执行过程

把算法读成一连串决策

Define directed/undirected and weighted/unweighted assumptions.

Choose the graph representation.

Track algorithm state and handle disconnected/cyclic cases explicitly.

记住一个小例子

Read a tiny input by hand and write down the state after every important operation. For Graph Depth-First Search, the goal is to make the invariant visible rather than to memorize code.

易读的 JavaScript 实现JavaScript

function dfs(graph, start) {
  const seen = new Set();
  function visit(node) {
    if (seen.has(node)) return;
    seen.add(node);
    for (const next of graph[node] ?? []) visit(next);
  }
  visit(start);
  return seen;
}

如何阅读这段代码

不要死记语法。跟踪每一行中发生变化的状态，并把它与上面描述的不变量联系起来。

复杂度

O(V+E)

Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.

何时使用

适用场景

Connectivity
Cycle/SCC building blocks
Backtracking-style graph exploration

常见错误

通常哪里会出错

Forgetting disconnected components.
Mixing weighted and unweighted shortest-path algorithms.
Not protecting against revisits/cycles.

面试中如何解释

专业回答结构

State the visited-set requirement and O(V + E). Compare with BFS when shortest unweighted paths are needed.

问题→核心思路→不变量 / 状态→Big-O→权衡

快速面试检查

What problem does Graph Depth-First Search solve?

DFS explores one path as deeply as possible before backtracking. It can be implemented recursively or with an explicit stack.

关于复杂度应该提到什么？

Its typical cost here is O(V+E), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.

最常见的错误是什么？

Forgetting disconnected components.

继续阅读Graph representationDFS/BFSPriority queues

function dfs(graph, start) { const seen = new Set(); function visit(node) { if (seen.has(node)) return; seen.add(node); for (const next of graph[node] ?? []) visit(next); } visit(start); return seen; }