PHP拓扑排序

拓扑排序是一种常见的图论算法，用于对有向无环图（DAG）进行排序。PHP 可以通过实现拓扑排序算法来解决该问题。

以下是一个 PHP 实现拓扑排序的示例代码：

function topological_sort($graph) {
    $visited = array();
    $stack = array();

    foreach ($graph as $node => $neighbors) {
        if (!isset($visited[$node])) {
            topological_sort_helper($graph, $node, $visited, $stack);
        }
    }

    return array_reverse($stack);
}

function topological_sort_helper($graph, $node, &$visited, &$stack) {
    $visited[$node] = true;

    foreach ($graph[$node] as $neighbor) {
        if (!isset($visited[$neighbor])) {
            topological_sort_helper($graph, $neighbor, $visited, $stack);
        }
    }

    array_push($stack, $node);
}

该函数接受一个邻接表形式的图并返回一个包含所有节点的拓扑排序列表。如果图不是有向无环图，则该算法无法正常工作。

例如，以下代码将一个邻接表传递给 topological_sort() 函数：

$graph = array(
    'A' => array('B', 'C', 'D'),
    'B' => array('E'),
    'C' => array('D', 'E'),
    'D' => array('F'),
    'E' => array('F'),
    'F' => array()
);

$sorted = topological_sort($graph);

运行该代码后，$sorted 将包含以下顺序的节点：A, B, C, D, E, F。