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