PHP を使用してトポロジカルソートアルゴリズムを作成する方法

<?php

function topologicalSort($graph) {
    $inDegree = []; // 入度数组
    $result = []; // 排序结果
    $queue = new SplQueue(); // 队列

    // 初始化入度数组
    foreach ($graph as $node => $neighbors) {
        $inDegree[$node] = 0;
    }

    // 计算入度数组
    foreach ($graph as $node => $neighbors) {
        foreach ($neighbors as $neighbor) {
            $inDegree[$neighbor]++;
        }
    }

    // 将入度为0的节点入队
    foreach ($inDegree as $node => $degree) {
        if ($degree == 0) {
            $queue->enqueue($node);
        }
    }

    // 队列不为空时
    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $result[] = $node;

        // 遍历邻居节点
        foreach ($graph[$node] as $neighbor) {
            $inDegree[$neighbor]--;
            if ($inDegree[$neighbor] == 0) {
                $queue->enqueue($neighbor);
            }
        }
    }

    // 判断是否成功排序
    if (count($result) == count($graph)) {
        return $result;
    } else {
        return false;
    }
}

// 测试用例
$graph = [
    'A' => ['B', 'C'],
    'B' => ['C', 'D'],
    'C' => ['E'],
    'D' => ['F'],
    'E' => [],
    'F' => ['G'],
    'G' => []
];

$result = topologicalSort($graph);
if ($result) {
    echo "拓扑排序结果: " . implode(' -> ', $result) . "
";
} else {
    echo "图中存在环，无法进行拓扑排序。
";
}

?>