PHP中拓扑排序算法的应用场景及实现方法探究。

/**
 * 构建有向图
 * @param array $edges 边集合
 * @return array
 */
function buildGraph(array $edges): array
{
    $graph = [];
    foreach ($edges as $edge) {
        [$from, $to] = $edge;
        if (!isset($graph[$from])) {
            $graph[$from] = [];
        }
        if (!isset($graph[$to])) {
            $graph[$to] = [];
        }
        $graph[$from][] = $to;
    }
    return $graph;
}

/**
 * 深度优先搜索
 * @param array $graph 有向图
 * @param array $visited 访问状态集合
 * @param int $node 当前节点编号
 * @param array $result 结果集合
 * @return bool 是否存在环
 */
function dfs(array $graph, array &$visited, int $node, array &$result): bool
{
    $visited[$node] = 1; // 标记节点为正在访问
    foreach ($graph[$node] as $next) {
        if ($visited[$next] == 1) {
            return true; // 存在环
        } elseif ($visited[$next] === 0) {
            if (dfs($graph, $visited, $next, $result)) {
                return true; // 存在环
            }
        }
    }
    $visited[$node] = 2; // 标记节点已访问完成
    $result[] = $node; // 将节点加入结果集
    return false; // 不存在环
}

/**
 * 执行拓扑排序
 * @param array $edges 边集合
 * @return array 排序结果
 */
function topologicalSort(array $edges): array
{
    $graph = buildGraph($edges);
    $n = count($graph);
    $visited = array_fill(0, $n, 0);
    $result = [];
    for ($i = 0; $i < $n; $i++) {
        if ($visited[$i] === 0 && dfs($graph, $visited, $i, $result)) {
            return []; // 存在环，排序失败
        }
    }
    return array_reverse($result); // 返回逆序排序结果
}