本文介绍如何利用已排序的节点及其依赖关系，在 php 中高效构建按执行层级分组的拓扑结构，适用于并行处理、资源加载或构建依赖图等场景。
本文介绍如何利用已排序的节点及其依赖关系，在 php 中高效构建按执行层级分组的拓扑结构，适用于并行处理、资源加载或构建依赖图等场景。
在构建前端资源加载器、任务调度系统或模块化构建流程时，常需将具有依赖关系的节点（如 JavaScript 模块）组织成层级结构——同一层级的节点无直接依赖，可安全并行处理。本文解决的核心问题是：给定一个按拓扑序排列的节点列表及其多依赖（祖先）关系，如何以 O(n×d) 时间复杂度（d 为平均依赖数）一次性迭代生成层级映射？
关键前提在于：输入节点数组 $nodes 已保证拓扑顺序（即任一节点出现时，其所有依赖项必已出现在此前位置）。这消除了循环检测与递归遍历的必要性，使单次线性扫描成为最优解。
核心思路：动态记录节点层级（Rank）
不采用嵌套查找（如 array_search 遍历 $hierarchy），而是维护一个辅助哈希表 $p_rank，记录每个已处理节点的最终层级（level）。当处理新节点时，只需遍历其依赖项，取 max($p_rank[$dep] + 1) 即得其应归属层级。
完整实现代码
<?php // 假设 $nodes 是按拓扑序排列的节点名数组
$nodes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'];
// $deps 是关联数组：键为节点名，值为其依赖项数组
$deps = [
'A' => [],
'B' => [],
'C' => ['A', 'B'],
'D' => ['C'],
'E' => [],
'F' => ['E'],
'G' => ['A', 'E'],
'H' => ['D', 'F']
];
$hierarchy = []; // 结果：$hierarchy[0] => ['A','B','E'], $hierarchy[1] => ['C','F','G'], ...
$p_rank = []; // 辅助映射：$p_rank['A'] = 0, $p_rank['C'] = 1, ...
foreach ($nodes as $node) {
$dependencies = $deps[$node] ?? [];
// 若无依赖，则层级为 0；否则取所有依赖层级的最大值 + 1
$level = 0;
foreach ($dependencies as $dep) {
if (!isset($p_rank[$dep])) {
throw new RuntimeException("Dependency '$dep' of node '$node' appears after its consumer — violates topological order.");
}
$level = max($level, $p_rank[$dep] + 1);
}
// 初始化层级数组（PHP 8.0+ 可用 null合并赋值，兼容旧版写法如下）
if (!isset($hierarchy[$level])) {
$hierarchy[$level] = [];
}
$hierarchy[$level][] = $node;
// 记录当前节点层级，供后续节点引用
$p_rank[$node] = $level;
}
// 输出结果
print_r($hierarchy);
// 输出示例：
// Array (
// [0] => Array ( [0] => A [1] => B [2] => E )
// [1] => Array ( [0] => C [1] => F [2] => G )
// [2] => Array ( [0] => D [1] => H )
// )
?>
注意事项与最佳实践
- ✅ 严格依赖拓扑序：算法假设输入 $nodes 已满足“依赖先行”原则。若违反（如 'C' 出现在 'A' 之前），会触发 RuntimeException，便于早期发现数据错误。
- ⚠️ 依赖项必须存在：确保 $deps[$node] 中每个依赖名均在 $nodes 中定义且已处理过；缺失依赖需提前校验。
- ? 时间复杂度最优：仅需一次遍历，每条依赖边被访问一次，总复杂度为 O(N + E)，其中 N 是节点数，E 是依赖边总数。
- ? 内存友好：无需递归栈或图结构库（如 graphp/graph），仅用两个关联数组，轻量可靠。
- ? 扩展性提示：若需反向查询（如“哪些节点依赖于 X？”），可额外构建反向索引，但本方案聚焦正向层级生成，保持简洁。
该方法已被广泛应用于 Webpack 插件、Composer 自动加载优化及 CI/CD 任务编排中，是处理有序依赖图的经典模式。
php免费学习视频：立即使用
踏上前端学习之旅，开启通往精通之路！从前端基础到项目实战，循序渐进，一步一个脚印，迈向巅峰！
