科技公司 SWE 在线评估：图与树的遍历不再慌
SWE Online Assessment: Graph and Tree Traversal Without the Panic
维护站点的编辑标准、披露规则，以及归档和活跃内容的修订流程。
摘要 Summary
图和树的题看着吓人，其实归结为一个很小的工具箱：无权图求最短步数用 BFS，探索或统计连通区域用 DFS，树的分层处理用层序遍历。这篇文章讲清每种什么时候用，并给一个大多数人都能改造的网格例子。
Graph and tree questions look intimidating but reduce to a small toolkit: BFS for shortest steps in an unweighted graph, DFS for exploring or counting connected regions, and level-order traversal for trees. This guide explains when to use each and a clean grid example most people can adapt.
图和树的题在很多在线评估里占到约五分之一，而它们给人的恐惧远大于实际难度。几乎所有这类题都归到一个很小的工具箱：无权图里求最少步数用广度优先（BFS），需要完整探索或统计连通区域用深度优先（DFS），而当树的问题在意深度时用层序遍历。选对与问题匹配的遍历方式，剩下的就只是记账。
这篇文章整理自公开、广为人知的算法题型，而不是某家公司的真实原题。把它当成一张练习地图：先记住每种题的识别信号，每个模式手里留一份干净的参考解法，剩下的时间用来把题读懂，读到能一眼选对套路。
BFS 还是 DFS：什么时候用哪个| BFS Versus DFS: When to Use Which
BFS 用队列一层一层地扩展，所以第一次到达某个节点时走的边最少——用于无权图里的最少步数。
DFS 用递归或栈尽可能往深走——用于完整探索、统计连通分量、或检测环。
对树来说，层序遍历就是 BFS；前序、中序、后序只是把「访问」放在 DFS 的不同时刻。
如果边有不同权重，单纯的 BFS 就不再给出最短路——那是 Dijkstra 的地盘，属于另一个话题。
最容易踩坑的几个细节| The Details That Trip People Up
始终维护一个 visited 集合，并在把节点入队时就标记，而不是出队时才标记，以免重复加入。
过深的递归会爆栈；对大图来说，用显式栈或迭代式 BFS 更安全。
在网格上，图是隐式的：每个格子的邻居是上下左右（或八个）相邻格子，并受边界限制。
一个例子：用 DFS 数岛屿| A Worked Example: Counting Islands With DFS
在一片由陆地和水组成的网格里数连通区域，是隐式图的经典题。遍历每个格子；当遇到还没访问过的陆地时，跑一次 DFS 把整座岛淹掉并标记，然后计数加一。每个格子只访问一次，所以整趟扫描是网格规模的线性时间。
def count_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
def sink(r, c):
# out of bounds or water: stop
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0" # mark visited by sinking the land
sink(r + 1, c)
sink(r - 1, c)
sink(r, c + 1)
sink(r, c - 1)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
sink(r, c)
islands += 1
return islandssink 开头的边界检查，正是让递归安全的关键；它既是递归的终止条件，也是边界守卫。在写那四个递归调用之前，先把这个不变量说清楚，并顺带提一句：在特别大的网格上，你会改用显式栈来避免深递归爆栈。
最容易失分的几个点| Common Mistakes That Cost Marks
干脆忘了 visited 集合，结果搜索在环上无限循环。
用 DFS 去做最短路径题，它探索得很深，却给不出最少步数。
在 BFS 里太晚标记访问，导致同一个节点多次进入队列。
处理网格边界出错，在第一行、最后一行或首尾列上触发越界。
一个够用的练习计划| A Focused Practice Plan
凭记忆各写一遍 BFS 和 DFS 模板，之后重复使用，让样板代码不再占用你的时间。
练一道网格题和一道点边图题，让隐式和显式两种形态都变得熟悉。
每道题，动手前先说清楚你要的是最少步数（BFS）还是完整探索（DFS）。
把一份递归 DFS 改写成迭代版，这样大输入下的爆栈就不会让你措手不及。
常见问题 FAQ
怎么快速决定用 BFS 还是 DFS？
How do I decide between BFS and DFS quickly?
如果问的是无权图里的最少步数，用 BFS。如果要你完整探索、统计区域或检测环，用 DFS。
网格题真的算图论题吗？
Do grid problems really count as graph problems?
算。网格是一张隐式图，每个格子和相邻格子相连。只要临时生成邻居，同样的 BFS、DFS 模板就能直接用。
BFS 什么时候就不再给出最短路径了？
When does BFS stop giving the shortest path?
一旦边有了不同的权重就不行了。普通 BFS 假设每条边代价相同；带权边要改用 Dijkstra 算法。
How This Article Was Produced
来源、审核和披露说明
- Source Type
- Editorially reviewed guidance built from public source material and manual synthesis.
- 基于公开资料和人工综合整理，并经过编辑复核的指南内容。
- AI Use
- AI-assisted drafting was used to organise notes and bilingual copy. A human editor reviewed structure, claims, and final wording before publication.
- AI 用于整理笔记和辅助双语表达。正式发布前，文章结构、关键判断和最终措辞均由人工编辑复核。
- What This Page Adds
- We condensed the material into decision-first guidance and surfaced the questions readers should answer before acting on the advice.
- 我们把资料压缩成以决策为先的指南，并补出了读者在采取行动前最该回答的关键问题。
For more on sourcing, corrections, and our recovery workflow, see Editorial Policy and Contact.
专题延伸阅读 Related Guides
按岗位方向、主题关键词和发布时间推荐，帮助读者从单篇文章进入完整准备路径。
SWE Online Assessment: Array and String Problems Made Approachable
科技公司 SWE 在线评估：数组与字符串题该怎么拆
Array and string questions are the single most common category in software-engineer online assessments. This guide explains the few patterns behind most of them — frequency counting, prefix sums, in-place editing, and single-pass parsing — and how to reach a clean, correct solution under time pressure.
SWE Online Assessment: Two Pointers and Sliding Window, From Scratch
科技公司 SWE 在线评估：双指针与滑动窗口从头讲清
Two pointers and sliding window turn many O(n^2) brute-force ideas into a single O(n) pass. This guide covers the three shapes you actually see — opposite ends, fast and slow, and a growing/shrinking window — with a clean example of the variable-size window that trips people up most.
SWE Online Assessment: Hash Map and Set Patterns
科技公司 SWE 在线评估：哈希表与集合题型精讲
Hash maps and sets buy you O(1) average lookups, and a surprising number of assessment problems are really about choosing the right key. This guide covers the complement trick, frequency maps, grouping by a signature, and using a seen-set to detect duplicates in one pass.
SWE Online Assessment: Dynamic Programming You Can Actually Derive
科技公司 SWE 在线评估：能自己推出来的动态规划
Dynamic programming feels hard because people memorise solutions instead of deriving them. This guide gives a repeatable four-step method — define the state, write the transition, set the base case, choose an order — and applies it to a clean climbing/coin example you can reuse.
Python Interview Prep for Data Science and Analytics: Solve the Common Patterns Cleanly
数据科学与分析岗 Python 面试：高频题不用炫技，先把常见模式写干净
Python interviews for data science and analytics roles usually focus on data handling, transformation, simple statistics, and whether you can explain your code. This guide groups the common challenge types and shows how to solve them cleanly without turning a straightforward task into something fragile.
Data Engineer Interview Guide: The Questions Behind SQL, Pipelines, and Reliability
数据工程师面试指南：SQL、管道和稳定性背后真正会被问什么
Data engineer interviews often look like a wall of unrelated questions until you group them by the decisions engineers actually make. This guide focuses on data modelling, pipeline design, operational reliability, and the judgement signals that separate a merely technical answer from a good engineering answer.