Comment écrire un algorithme de tri topologique en utilisant PHP

Comment écrire un algorithme de tri topologique en utilisant PHP

Le tri topologique est un algorithme de tri de graphes acycliques dirigés (DAG). Son principe est de trier les nœuds du graphe en fonction de dépendances pour garantir que les directions de toutes les arêtes dans les résultats du tri sont cohérentes. Dans le développement réel, le tri topologique est souvent utilisé pour résoudre des problèmes tels que la planification des tâches et l'analyse des dépendances. Cet article explique comment écrire un algorithme de tri topologique en utilisant PHP, avec des exemples de code.

Idée d'algorithme :

1. Créez un tableau en degrés pour enregistrer le degré en de chaque nœud (c'est-à-dire combien de nœuds pointent vers ce nœud) 
2. Créez un tableau de résultats pour enregistrer les résultats du tri ; Traverse Pour les nœuds du graphique, calculez le degré en entrée de chaque nœud et stockez-le dans le tableau en degré ;
3. Initialisez une file d'attente et ajoutez tous les nœuds avec un degré en entrée de 0 à la file d'attente ; la file d'attente n'est pas vide, retirez séquentiellement un nœud de la file d'attente et ajoutez-le au tableau de résultats ;
4. Parcourez les nœuds voisins du nœud et réduisez le degré d'entrée de chaque nœud voisin de 1 
5. Si le degré d'entrée de ; le nœud voisin est réduit à 0, puis mettez-le en file d'attente ;
6. Répétez les étapes 5 à 7 jusqu'à ce que la file d'attente soit vide
7. Si le nombre de nœuds dans le tableau résultat est égal au nombre de nœuds dans le graphique, le tri est effectué. réussi ; sinon, il y a un cycle dans le graphique et le tri topologique ne peut pas être effectué.
8. Ce qui suit est un exemple de code de l'algorithme de tri topologique PHP écrit sur la base des idées ci-dessus :

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

Dans le code ci-dessus,

dans le tableau. Après avoir exécuté le code, les résultats du tri topologique seront affichés.

Résumé :

Cet article présente comment utiliser PHP pour écrire un algorithme de tri topologique et donne des exemples de code correspondants. Le tri topologique est un algorithme pratique souvent utilisé pour résoudre des problèmes tels que la planification des tâches. La maîtrise de l'algorithme de tri topologique contribuera à améliorer les capacités de traitement des graphes acycliques dirigés et à prendre en charge diverses analyses de dépendances au cours du développement. J'espère que cet article vous sera utile. $graph表示有向图中的节点和它们的邻居节点的关系。我们通过调用topologicalSort函数来对图进行拓扑排序，返回排序结果或者判断是否存在环。在上述示例中，图中的节点为A、B、C、D、E、F、G，对应的邻居节点关系定义在$graph

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!