让提交历史先展示后代，再展示祖先
Git 的拓扑历史遍历记录尚未输出的子提交数量；只有相关子提交都已处理，父提交才进入可输出集合。
工程问题#
提交时间不一定严格反映父子关系；仅按时间排序可能在一个分支的后代尚未显示时就先显示共同祖先，使历史关系难以阅读。
实际实现#
topo_walk 用 exploration 和 indegree 两个队列发现图并统计边，输出提交后递减其父提交的计数。这里计数采用加一编码：1 表示已经发现且没有未处理子提交，0 用于未初始化或已输出状态。降到 1 的父提交被加入 topo_queue。
处理流程#
- 解析当前遍历范围内的提交及父边，准备入度计数
- 选择当前可输出的提交
- 输出后递减各父提交的未处理子边计数
- 计数降到可输出状态后，把父提交加入候选集合
源码片段#
固定版本 · 原文摘录3867 generation = commit_graph_generation(parent);3868 if (generation < info->min_generation) {3869 info->min_generation = generation;3870 compute_indegrees_to_depth(revs, info->min_generation);3871 }38723873 pi = indegree_slab_at(&info->indegree, parent);38743875 (*pi)--;3876 if (*pi == 1)3877 prio_queue_put(&info->topo_queue, parent);38783879 if (revs->first_parent_only)3880 return;当探索走到更低 generation 时补足计数，然后递减父提交入度；计数等于 1 而非 0 时入候选队列，源于该实现的加一编码。
片段是遍历循环中的父边处理部分；计数初始化、候选队列模式和 limited 分支在同一文件中。
收益与取舍#
工程分析带来的收益
- 保证所遍历提交中父提交不会先于其相关子提交输出
- 可结合 generation number 分阶段探索，避免总是先完整展开历史
付出的代价
- 合并提交、历史过滤和 first-parent 会改变本次遍历涉及的边，必须按同一规则计数
- 不能把整体实现简单计为教科书 FIFO 队列的 O(V+E)：对象解析、优先队列与历史探索均有额外成本
可比较的选择
只按提交时间降序实现与理解较直接，但时间戳不保证与提交依赖关系一致。
版本与适用范围#
对应 Git v2.46.0 在非 limited 的 topo_order 遍历中使用的 topo_walk 路径，边按子提交指向父提交理解。topo_queue 在默认图顺序模式是栈式行为，在日期排序模式有比较器，不能统一称为 FIFO 或堆。
参考来源#
源码、官方文档与原始论文revision.c · init_topo_walk / indegree_walk_step / expand_topo_walk
相关实现与比较#
4 个相关案例HNSW 从稀疏上层快速定位区域，再在底层扩大候选搜索。
借助计算依赖图与使用者计数，清理既不影响输出也无副作用的节点。
Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS，检查跳转目标、可达性及控制流结构。
LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器，将相互递归的函数作为一组，并按被调用方优先的顺序处理分组。