本文介绍一种高效、非递归的方法，利用节点的拓扑顺序特性，将扁平的依赖关系数组转换为按执行层级分组的二维结构，适用于并行处理、资源加载等场景。
本文介绍一种高效、非递归的方法，利用节点的拓扑顺序特性，将扁平的依赖关系数组转换为按执行层级分组的二维结构，适用于并行处理、资源加载等场景。
在构建前端资源加载器、任务调度系统或模块化构建流程时，常需将具有依赖关系的节点（如 JavaScript 模块）组织成层级结构：同一层级的节点无相互依赖，可安全并行处理；下一层级的节点仅依赖于上一层或更早层的节点。PHP 中若已获得严格拓扑排序的节点列表（即每个节点出现时，其所有依赖项均已出现在此前位置），则无需图算法或递归遍历，仅需一次线性扫描即可完成层级构建。
核心思路是：为每个节点动态计算其“最小执行层级”（level），该层级等于其所有依赖节点的最大层级 + 1；若无依赖，则层级为 0。关键优化在于使用辅助哈希表 $p_rank 缓存每个已处理节点的层级，使依赖查找降为 O(1) 时间复杂度，整体算法时间复杂度为 O(N + D)，其中 N 为节点总数，D 为所有依赖项总数。
以下是完整、健壮的实现代码：
<?php
// 输入示例（实际中来自第三方库）
$nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'];
// 模拟 $foreign_obj->reqs 结构：键为节点名，值为包含 reqs 数组的对象
$foreign_obj = new stdClass();
$foreign_obj->reqs = [
'A' => (object)['name' => 'A', 'src' => '/path/to/A.js', 'reqs' => []],
'B' => (object)['name' => 'B', 'src' => '/path/to/B.js', 'reqs' => []],
'C' => (object)['name' => 'C', 'src' => '/path/to/C.js', 'reqs' => ['A', 'B']],
'D' => (object)['name' => 'D', 'src' => '/path/to/D.js', 'reqs' => ['C']],
'E' => (object)['name' => 'E', 'src' => '/path/to/E.js', 'reqs' => []],
'F' => (object)['name' => 'F', 'src' => '/path/to/F.js', 'reqs' => ['E']],
'G' => (object)['name' => 'G', 'src' => '/path/to/G.js', 'reqs' => ['A', 'E']],
'H' => (object)['name' => 'H', 'src' => '/path/to/H.js', 'reqs' => ['D', 'F', 'G']],
];
// 构建层级结构
$hierarchy = [];
$p_rank = []; // 存储每个节点的层级（rank），用于 O(1) 查找
foreach ($nodes as $node) {
// 获取当前节点的依赖列表
$dependencies = $foreign_obj->reqs[$node]->reqs ?? [];
// 初始层级为 0（无依赖时即为第 0 层）
$level = 0;
// 遍历所有依赖，取其最大层级 + 1
foreach ($dependencies as $dep) {
if (!isset($p_rank[$dep])) {
throw new InvalidArgumentException("Dependency '$dep' for node '$node' appears before its definition — violates topological order.");
}
$level = max($level, $p_rank[$dep] + 1);
}
// 将节点加入对应层级数组（自动初始化空数组）
$hierarchy[$level] = $hierarchy[$level] ?? [];
$hierarchy[$level][] = $node;
// 记录当前节点层级，供后续节点依赖查找
$p_rank[$node] = $level;
}
// 输出结果（符合预期格式）
echo "Level-based hierarchy:\n";
foreach ($hierarchy as $level => $nodesAtLevel) {
echo "| {$level} | " . implode(',', $nodesAtLevel) . " |\n";
}
?>输出示例：
立即学习“PHP免费学习笔记（深入）”；
Level-based hierarchy: | 0 | A,B,E | | 1 | C,F,G | | 2 | D | | 3 | H |
✅ 优势说明：
- 线性时间复杂度：单次遍历，无递归、无嵌套搜索；
- 内存友好：仅维护两个关联数组，空间复杂度 O(N)；
- 强健性保障：显式检查依赖是否存在 $p_rank 中，及时捕获违反拓扑序的异常数据；
- 可扩展性强：支持多依赖、跨层级依赖（如 G 同时依赖 A 和 E）、空依赖等边界情况。
⚠️ 注意事项：
- 此方案严格依赖输入列表的拓扑有序性。若第三方库未保证此性质，需先进行 Kahn 算法或 DFS 拓扑排序预处理；
- 若 $foreign_obj->reqs 中存在缺失节点（如某节点未定义 reqs 属性），应添加 ?? [] 默认值或前置校验；
- 实际生产环境建议封装为可复用函数，并增加类型提示与文档注释。
通过该方法，你不仅能精准生成层级分组，还能自然获得每个节点的执行序号（level），为后续调度、可视化或缓存策略提供坚实基础。
