图题的基础是明确节点身份、邻接关系、访问标记时机，以及遍历全部状态还是寻找最短路径。

🧭 什么时候考虑这个专题

无权最短步数使用 BFS；遍历连通分量可用 BFS 或 DFS；依赖顺序使用拓扑排序。

开始编码前先明确输入、输出、数据规模和允许修改的数据，再用一句话写出循环、窗口、堆或递归函数保持的不变量。

核心结构与复杂度

知识点核心规则常见复杂度
visited 标记时机BFS 通常在节点入队时立即标记访问遍历 O(V+E)
无权最短路BFS 按边数分层，第一次到达节点即得到无权最短距离O(V+E)
递归 DFS 栈风险递归 DFS 的调用栈深度可达到顶点数量空间 O(V)
邻接表遍历邻接表完整遍历会访问每个顶点和每条边常数次O(V+E)
拓扑排序与环Kahn 算法处理的顶点数少于总数时图中存在环O(V+E)

复杂度必须对应真实代码路径。哈希结构要区分平均与最坏情况，递归要计算调用栈，返回结果是否计入空间也应按题目口径说明。

适用边界

  • visited 标记时机： 出队时才标记可能让同一节点重复进入队列
  • 无权最短路： 存在不同边权时需要 Dijkstra 等算法
  • 递归 DFS 栈风险： 深图或长链应考虑显式栈
  • 邻接表遍历： 无向图通常把每条边存储两次但数量级不变
  • 拓扑排序与环： 拓扑顺序只适用于有向无环图

C# 实现检查

  1. 方法签名与题目契约一致，不依赖控制台输入输出。
  2. 数值计算检查 int 溢出，必要时先提升为 long。
  3. 集合选择说明平均复杂度、顺序语义和重复值处理。
  4. 字符串题明确使用 char、Rune、序号比较还是文化比较。
  5. 递归题说明终止条件、最大深度和退化输入。

⚠️ 常见误区

  • visited 标记时机： 不要把“只要最终有 visited，何时标记都不会影响开销”当成规则。
  • 无权最短路： 不要把“DFS 第一次到达目标也保证路径最短”当成规则。
  • 递归 DFS 栈风险： 不要把“DFS 使用递归就不需要计算额外空间”当成规则。
  • 邻接表遍历： 不要把“图遍历一律是 O(V²)”当成规则。
  • 拓扑排序与环： 不要把“任意有向图都至少存在一种拓扑顺序”当成规则。

练习顺序

先完成本组 5 道选择题，口述每个选项的边界；再独立实现编程题，最后对照参考答案检查不变量、复杂度和面试追问。