So schreiben Sie einen topologischen Sortieralgorithmus mit PHP

So schreiben Sie einen topologischen Sortieralgorithmus mit PHP

Topologische Sortierung ist ein Algorithmus zum Sortieren gerichteter azyklischer Graphen (DAG). Sein Prinzip besteht darin, die Knoten im Diagramm nach Abhängigkeiten zu sortieren, um sicherzustellen, dass die Richtungen aller Kanten in den Sortierergebnissen konsistent sind. In der tatsächlichen Entwicklung wird die topologische Sortierung häufig zur Lösung von Problemen wie der Aufgabenplanung und der Abhängigkeitsanalyse verwendet. In diesem Artikel wird anhand von Codebeispielen erläutert, wie man mit PHP einen topologischen Sortieralgorithmus schreibt.

Algorithmusidee:

1. Erstellen Sie ein In-Grad-Array, um den In-Grad jedes Knotens zu speichern (d. h. wie viele Knoten auf diesen Knoten verweisen);
2. Erstellen Sie ein Ergebnisarray, um die Sortierergebnisse zu speichern;
3. Berechnen Sie für die Knoten im Diagramm den In-Grad jedes Knotens und speichern Sie ihn im In-Grad-Array.
4. Initialisieren Sie eine Warteschlange und fügen Sie alle Knoten mit einem In-Grad von 0 zur Warteschlange hinzu Warteschlange ist nicht leer, entfernen Sie nacheinander einen Knoten aus der Warteschlange und fügen Sie ihn dem Ergebnisarray hinzu.
5. Durchlaufen Sie die Nachbarknoten des Knotens und reduzieren Sie den In-Grad jedes Nachbarknotens um 1 Der Nachbarknoten wird auf 0 reduziert und dann in die Warteschlange gestellt.
6. Wiederholen Sie die Schritte 5 bis 7, bis die Warteschlange leer ist.
7. Wenn die Anzahl der Knoten im Ergebnisarray der Anzahl der Knoten im Diagramm entspricht, erfolgt die Sortierung Erfolgreich; andernfalls gibt es einen Zyklus im Diagramm und die topologische Sortierung kann nicht durchgeführt werden.
8. Das Folgende ist ein Codebeispiel des topologischen PHP-Sortieralgorithmus, der auf der Grundlage der oben genannten Ideen geschrieben wurde:

9. <?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 "图中存在环，无法进行拓扑排序。
   ";
   }
   
   ?>

Im obigen Code,

im Array. Nach dem Ausführen des Codes werden die Ergebnisse der topologischen Sortierung ausgegeben.

Zusammenfassung:

Dieser Artikel stellt vor, wie man PHP zum Schreiben eines topologischen Sortieralgorithmus verwendet, und gibt entsprechende Codebeispiele. Die topologische Sortierung ist ein praktischer Algorithmus, der häufig zur Lösung von Problemen wie der Aufgabenplanung verwendet wird. Die Beherrschung des topologischen Sortieralgorithmus wird dazu beitragen, die Verarbeitungsfähigkeiten gerichteter azyklischer Graphen zu verbessern und verschiedene Abhängigkeitsanalysen während der Entwicklung zu unterstützen. Ich hoffe, dieser Artikel ist hilfreich für Sie. $graph表示有向图中的节点和它们的邻居节点的关系。我们通过调用topologicalSort函数来对图进行拓扑排序，返回排序结果或者判断是否存在环。在上述示例中，图中的节点为A、B、C、D、E、F、G，对应的邻居节点关系定义在$graph

Das obige ist der detaillierte Inhalt vonSo schreiben Sie einen topologischen Sortieralgorithmus mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!