本文介绍如何基于已排序的节点及其多依赖关系（非单父级），在 php 中线性遍历生成层级索引数组，使同层节点可并行处理，时间复杂度 o(n+m)，无需递归或图库。
本文介绍如何基于已排序的节点及其多依赖关系（非单父级），在 php 中线性遍历生成层级索引数组，使同层节点可并行处理，时间复杂度 o(n+m)，无需递归或图库。
在前端资源加载、构建系统或任务调度等场景中，常需将具有多前置依赖（requires）的扁平节点列表转换为按执行层级组织的结构——即：每个层级包含所有就绪节点（其所有依赖均已出现在更浅层级中）。关键前提是：输入节点数组严格按拓扑序排列（任一节点出现时，其全部依赖必已出现），这使我们能用一次线性扫描完成分层，避免图遍历或递归回溯。
核心思路是动态维护两个映射：
- $hierarchy[$level]：存储第 $level 层的所有节点（如 ['A','B','E']）；
- $p_rank[$node]：记录每个节点所属的层级（用于快速查依赖深度）。
对每个节点，其层级 = 所有依赖节点层级的最大值 + 1；若无依赖，则层级为 0。由于输入有序，每次访问依赖时，$p_rank 中必已存在其层级信息。
以下是完整、健壮的实现代码：
立即学习“PHP免费学习笔记（深入）”；
<?php
// 假设 $nodes 是节点名数组（如 ['A','B','C',...]）
// $foreign_obj->reqs 是以节点名为键的对象数组，每个对象含 ->reqs（依赖名数组）
$hierarchy = [];
$p_rank = []; // 节点 → 层级映射
foreach ($nodes as $node) {
// 获取当前节点的直接依赖列表（确保为数组，兼容空/缺失情况）
$dependencies = [];
if (isset($foreign_obj->reqs[$node]) && is_array($foreign_obj->reqs[$node]->reqs)) {
$dependencies = $foreign_obj->reqs[$node]->reqs;
}
// 计算当前节点应处的层级：max(各依赖层级) + 1；无依赖则为 0
$level = 0;
foreach ($dependencies as $dep) {
if (isset($p_rank[$dep])) {
$level = max($level, $p_rank[$dep] + 1);
}
// 注意：因输入保证拓扑序，$dep 必已在 $p_rank 中，此处 isset 检查为防御性编程
}
// 初始化该层级数组（PHP 7.4+ 可用 $hierarchy[$level] ??= []）
if (!isset($hierarchy[$level])) {
$hierarchy[$level] = [];
}
$hierarchy[$level][] = $node;
$p_rank[$node] = $level; // 记录层级，供后续节点依赖查询
}
// 输出结果（层级从 0 开始，每层内节点顺序与输入一致）
print_r($hierarchy);
// 示例输出：
// Array (
// [0] => Array ( [0] => A, [1] => B, [2] => E )
// [1] => Array ( [0] => C, [1] => F )
// [2] => Array ( [0] => D )
// )✅ 优势说明：
- 时间效率：O(N + D)，N 为节点数，D 为总依赖数；无嵌套循环查找，$p_rank 提供 O(1) 依赖层级查询；
- 空间简洁：仅需两个关联数组，无递归栈开销；
- 鲁棒性强：显式处理空依赖、未定义依赖字段等边界情况；
- 符合约束：完全依赖输入的拓扑序保证，不校验环路（题目已承诺无环）。
⚠️ 注意事项：
- 若实际数据不满足“输入有序”前提，此算法将出错（如依赖未被提前处理），建议上线前添加简单校验（例如遍历中检测 $p_rank[$dep] 是否缺失并抛出异常）；
- $hierarchy 的键为整数层级，天然支持 foreach 并行处理各层（如 array_map(..., $hierarchy[0])）；
- 如需反向构建树形结构（父→子），可在本算法基础上额外维护 $children[$parent][] = $child，但本场景无需。
该方案优雅地将拓扑分层问题降维为一次动态规划式扫描，是处理有序多依赖扁平数据的推荐实践。
