PHP实现控制器拓扑排序 按优先级与依赖规则处理加载顺序

PHP控制器拓扑排序完整实现 #

实现逻辑 #

完全匹配需求的4个处理步骤，结合Kahn拓扑排序算法实现，选择入度为0的节点时优先按优先级升序选取，同时覆盖无效节点过滤逻辑：

1. 解析原始配置，拆分每个控制器的优先级和依赖列表
2. 过滤所有依赖不存在的控制器
3. 检测并过滤存在循环依赖的控制器
4. 剩余有效节点通过Kahn算法排序，既保证优先级高的先加载，也满足被依赖控制器优先加载的要求

完整实现代码 #

<?php
// 原始控制器配置
$controllers = [
    "controller_3" => "3",
    "controller_1" => "1:controller_2",
    "controller_2" => "2",
    "controller_4" => "1:controller_2&controller_1",
    "controller_x" => "2:controller_not_exists",
    "controller_loopexit1" => "4:controller_loopexit2",
    "controller_loopexit2" => "5:controller_loopexit1"
];

// 1、解析配置生成控制器元信息
$controllerMeta = [];
foreach ($controllers as $name => $config) {
    $parts = explode(':', $config, 2);
    $priority = intval($parts[0]);
    $dependencies = isset($parts[1]) ? explode('&', $parts[1]) : [];
    $controllerMeta[$name] = [
        'priority' => $priority,
        'deps' => $dependencies
    ];
}

// 2、过滤依赖不存在的控制器
$validControllers = [];
foreach ($controllerMeta as $name => $meta) {
    $hasInvalidDep = false;
    foreach ($meta['deps'] as $dep) {
        if (!isset($controllerMeta[$dep])) {
            $hasInvalidDep = true;
            break;
        }
    }
    if (!$hasInvalidDep) {
        $validControllers[$name] = $meta;
    }
}

// 3、检测并过滤存在循环依赖的控制器
function hasCycle(string $node, array $graph, array &$visited, array &$recStack): bool {
    if (!isset($visited[$node])) {
        $visited[$node] = true;
        $recStack[$node] = true;
        foreach ($graph[$node]['deps'] as $dep) {
            if (!isset($visited[$dep]) && hasCycle($dep, $graph, $visited, $recStack)) {
                return true;
            } elseif (isset($recStack[$dep])) {
                return true;
            }
        }
    }
    unset($recStack[$node]);
    return false;
}
$cycleNodes = [];
$validCopy = $validControllers;
foreach (array_keys($validCopy) as $name) {
    $visited = [];
    $recStack = [];
    if (hasCycle($name, $validCopy, $visited, $recStack)) {
        foreach (array_keys($recStack) as $cycleNode) {
            $cycleNodes[$cycleNode] = true;
        }
    }
}
foreach (array_keys($cycleNodes) as $cycleNode) {
    unset($validControllers[$cycleNode]);
}

// 4、Kahn拓扑排序，同入度节点按优先级升序选取
$inDegree = [];
$adj = [];
foreach ($validControllers as $name => $meta) {
    $inDegree[$name] = count($meta['deps']);
    foreach ($meta['deps'] as $dep) {
        $adj[$dep][] = $name;
    }
}
// 初始化入度为0的队列，按优先级排序
$queue = [];
foreach ($validControllers as $name => $meta) {
    if ($inDegree[$name] == 0) {
        $queue[] = $name;
    }
}
usort($queue, function($a, $b) use ($validControllers) {
    return $validControllers[$a]['priority'] - $validControllers[$b]['priority'];
});

$sorted = [];
while (!empty($queue)) {
    $current = array_shift($queue);
    $sorted[] = $current;
    if (isset($adj[$current])) {
        foreach ($adj[$current] as $neighbor) {
            $inDegree[$neighbor]--;
            if ($inDegree[$neighbor] == 0) {
                $queue[] = $neighbor;
                // 每次新增入度为0的节点后重新按优先级排序
                usort($queue, function($a, $b) use ($validControllers) {
                    return $validControllers[$a]['priority'] - $validControllers[$b]['priority'];
                });
            }
        }
    }
}

// 输出结果
foreach ($sorted as $controller) {
    echo $controller . PHP_EOL;
}
?>

运行输出结果 #

controller_2
controller_1
controller_4
controller_3

和预期输出完全一致。

内容的提问来源于stack exchange，提问作者Luc Laverdure