LeetCode 841中等图 · DFS
钥匙和房间 图解题解
这道题到底在问什么
每个房间里放着若干钥匙，每把钥匙通往一个房间。从 0 号房开始，问能否访问到所有房间？
- rooms
- [[1], [2], [3], []]
- 输出
- true
最优解：一步一步想明白
- 3最朴素的想法：维护一堆已拿到的钥匙，每轮扫一遍看能开哪些还没开的门。可你会一次次重新检查那些早就开过的房间，钥匙一多就大量重复。
- 4转折：把它看成图——房间是节点，钥匙是有向边。从 0 开始 BFS/DFS，每进一个房就立刻标记 visited，只对没访问过的房入队。这样每个房只处理一次，不再回头重扫。最后数 visited 等于房间总数就是 true。
- 5queue=[0]画成图：rooms[0]=[1]、rooms[1]=[2]、rooms[2]=[3]、rooms[3]=[]，即三条有向边 0→1→2→3。起点 0 标记 visited 并入队，作为遍历的源头。
- 6visited={0}取出 0（标橙=正在处理），它已访问。看它手上的钥匙 rooms[0]=[1]，准备去开 1 号房。
- 7visited={0,1}沿边 0→1：房 1 还没访问，所以拿钥匙开门、标记 visited、入队。0 处理完变绿（done）。
- 8visited={0,1}取出 1 处理。它的钥匙 rooms[1]=[2]，指向房 2。
- 9visited={0,1,2}沿边 1→2：房 2 没访问过，开门、标记、入队。注意每次进房第一件事就是标 visited——这是防止绕回来死循环的关键。
- 10visited={0,1,2}取出 2 处理，它的钥匙 rooms[2]=[3]。设想此刻又冒出一把指回 1 的钥匙：房 1 已经在 visited 里——直接跳过、不再入队。这就是负例：已访问的房一律不重复处理。
- 11visited={0,1,2,3}沿边 2→3：房 3 没访问，开门、标记、入队。
- 12visited={0,1,2,3}取出 3 处理，rooms[3]=[] 没钥匙了。没有新房可入队，队列空，遍历结束。
- 134 == 4 → true数一下 visited：4 个，正好等于房间总数 4 → 全部可达，返回 true。若某房没人给钥匙、永远进不了 visited，最终 len(visited) 小于 N，就返回 false。
- 16凡是「从一个点出发能不能走到所有点」「有几个连通块」，都用 BFS/DFS 数可达节点。钥匙房间、被围绕的区域、省份数量，全是这一类。
⚠️ 容易写错的地方
✗ 错：入队 / 进 dfs 才忘标 visited
✓ 对：加入 visited 和入队同时做
不标记遇到指回来的钥匙会重复入队，有环时无限循环
✗ 错：判断只看「有没有到某个终点」
✓ 对：比对 len(visited) == len(rooms)
题目要的是访问到全部房间，不是到达某一个
完整代码（Python）
Python
class Solution:
def canVisitAllRooms(self, rooms):
seen = {0}
stack = [0]
while stack:
room = stack.pop()
for key in rooms[room]:
if key not in seen:
seen.add(key)
stack.append(key)
return len(seen) == len(rooms)套路模板 · 图可达性遍历（背下来）
# 「从起点能到达哪些点」都套
visited = {start}; q = deque([start])
while q:
u = q.popleft()
for v in graph[u]:
if v not in visited: # 只走没访问的
visited.add(v); q.append(v)
# len(visited) == N ? 全连通复杂度
时间复杂度
O(N+E)
N 个房各出队一次，E 把钥匙各检查一次
空间复杂度
O(N)
visited 集合 + 队列最多装 N 个房
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 钥匙和房间 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「DFS」，换最直接的暴力解会差在哪？+
DFS抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。