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

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

トポロジカル ソートは、有向非巡回グラフ (DAG) をソートするためのアルゴリズムです。その原理は、依存関係に従ってグラフ内のノードを並べ替え、並べ替え結果内のすべてのエッジの方向が一貫していることを確認することです。実際の開発では、トポロジカルソートはタスクのスケジューリングや依存関係の分析などの問題を解決するためによく使用されます。この記事では、PHP を使用してトポロジカル ソート アルゴリズムを作成する方法をコード例とともに紹介します。

アルゴリズムのアイデア:

1. 各ノードの次数 (つまり、ノードを指すノードの数) を保存するための次数配列を作成します。
2. 結果配列を作成して並べ替え結果を保存します;
3. グラフ内のノードをトラバースし、各ノードの次数を計算し、それを次数配列に保存します;
4. キューを初期化し、入次数 0 のすべてのノードをキューに入れます;
5. キューが空でない場合は、キューから 1 つのノードを順番にデキューし、それを結果配列に追加します;
6. Traverse このノードの隣接ノードについて、各隣接ノードの入次数を 1 ずつ減らします。
7. 隣接ノードの入次数が 0 に減った場合は、それをキューに追加します。
8. キューが空になるまで手順 5 ～ 7 を繰り返します。
9. 結果の配列内のノードの数がグラフ内のノードの数と等しい場合、並べ替えは成功します。それ以外の場合は、並べ替えが成功します。 、グラフ内に循環があり、トポロジカルソートが実行できません。

以下は、上記の考え方に基づいて作成された 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 "图中存在环，无法进行拓扑排序。
";
}

?>

上記のコードでは、$graph は有向グラフ ノードとその隣接ノード間の関係。 topologicalSort 関数を呼び出してグラフ上でトポロジカル ソートを実行し、ソート結果を返すか、サイクルがあるかどうかを判断します。上記の例では、グラフ内のノードは A、B、C、D、E、F、G であり、対応する隣接ノード関係が $graph 配列で定義されています。コードを実行すると、トポロジカルソートの結果が出力されます。

概要:
この記事では、PHP を使用してトポロジカル ソート アルゴリズムを作成する方法を紹介し、対応するコード例を示します。トポロジカル ソートは、タスク スケジューリングなどの問題を解決するためによく使用される実用的なアルゴリズムです。トポロジカルソートアルゴリズムを習得すると、有向非巡回グラフの処理能力が向上し、開発中のさまざまな依存関係分析をサポートできるようになります。この記事がお役に立てば幸いです。

以上がPHP を使用してトポロジカルソートアルゴリズムを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。