推荐用邻接表（dict存子节点）配合parent_map和depth_cache实现高效层级查询：查祖先靠parent_map迭代，查子孙用带深度的BFS，增删边时需同步更新depth_cache以防层级错误。
邻接表怎么存父子关系才方便查层级？
直接用 dict 套 list 存边不够——查某节点的所有祖先或子孙时得反复递归遍历，效率低还容易漏层。真正要支持层级查询，得在基础邻接表上额外维护「深度」或「路径信息」，但又不能每次查询都全图遍历。
推荐做法：用 dict 存邻接关系（graph[node] = [child1, child2]），再配合一个单独的 parent_map（{child: parent}）和一个缓存用的 depth_cache（{node: int}）。这样查任意节点的直系祖先、子孙、同级节点都能在 O(1) 或 O(层级深度) 内完成，不用每次都 DFS。
- 只在插入边时更新
parent_map和depth_cache，避免查询时重复计算 - 如果图可能含环，插入前必须检测环（比如用 DFS 标记 visiting/visited 状态）
-
depth_cache初始值设为-1，未计算过深度的节点保持该值，避免误判
如何快速获取某个节点的所有祖先（向上遍历）？
靠 parent_map 迭代往上跳就行，比 DFS 安全且快。关键点是别忘了处理根节点（没有 parent 的节点）作为终止条件。
def get_ancestors(graph, parent_map, node):
ancestors = []
current = node
while current in parent_map:
current = parent_map[current]
ancestors.append(current)
return ancestors
- 返回的是从父节点开始、按层级由近到远排列的列表，不包含自己
- 如果想包含自身，调用时手动加
[node] + get_ancestors(...) - 若需去重（比如有 DAG 中多条路径指向同一祖先），外面套一层
list(dict.fromkeys(...))
查所有子孙节点（向下遍历）为什么不能只靠 BFS？
BFS 能列出所有可达节点，但默认不带层级信息；而“第 N 层子孙”这种需求，BFS 队列里必须存 (node, depth) 元组，否则没法区分层级边界。
立即学习“Python免费学习笔记（深入）”；
from collections import deque
def get_descendants_by_depth(graph, root, max_depth=None):
if root not in graph:
return []
queue = deque([(root, 0)])
result = {}
while queue:
node, depth = queue.popleft()
if max_depth is not None and depth > max_depth:
continue
if depth not in result:
result[depth] = []
result[depth].append(node)
for child in graph.get(node, []):
queue.append((child, depth + 1))
return result
-
result是{0: [root], 1: [child1, child2], ...}形式，方便按需取某一层 - 如果只要扁平化列表（不分层），把
result改成 list，每次 appendnode即可 - 注意：这个函数不检查环，DAG 或树结构下安全；有环必须加 visited 集合
修改边时为什么必须同步更新 depth_cache？
删掉一个父节点或移动子树位置后，整棵子树的深度都变了，但没人会自动通知你。不手动重算，后续所有基于 depth_cache 的判断（比如“是否在同一层”）都会出错。
- 删除边时：先找出被删子节点的所有子孙（用上面的
get_descendants_by_depth），然后对每个子孙调用depth_cache.pop(node, None) - 移动子树（即先删后加）：新 parent 的 depth 已知，那么新子树根节点 depth =
depth_cache[new_parent] + 1，再 BFS 更新整棵子树 - 最省事但稍慢的做法：删边/改边后清空整个
depth_cache，下次查询时懒加载重算——适合变更不频繁的场景
层级查询看着只是“多存几个数”，实际所有缓存字段都得跟着拓扑变化联动更新，漏掉任何一个环节，查出来的层级关系就不可信。
