Comment écrire un algorithme de recherche en profondeur pour les graphiques en utilisant PHP

Comment écrire un algorithme de recherche en profondeur pour un graphique à l'aide de PHP

La recherche en profondeur (DFS) est un algorithme de traversée de graphique qui explore aussi profondément que possible le long d'une branche du graphique jusqu'à ce qu'il ne soit plus possible de continuer. Revenez ensuite au nœud précédent et continuez à explorer les autres branches jusqu'à ce que tous les nœuds aient été visités. Dans cet article, nous apprendrons comment écrire un algorithme de recherche en profondeur pour les graphiques à l'aide de PHP.

Tout d'abord, nous créons une classe de nœuds pour représenter les nœuds dans le graphique :

class Node {
   public $value;
   public $visited;
   public $neighbors;

   public function __construct($value) {
      $this->value = $value;
      $this->visited = false;
      $this->neighbors = array();
   }

   public function addNeighbor($neighbor) {
      array_push($this->neighbors, $neighbor);
   }
}

Chaque nœud a une valeur, une balise visitée et un tableau de voisins. Dans le constructeur, nous initialisons ces propriétés.

Ensuite, nous créons une classe de graphe et implémentons l'algorithme de recherche en profondeur :

class Graph {
   public $nodes;

   public function __construct() {
      $this->nodes = array();
   }

   public function addNode($value) {
      $node = new Node($value);
      array_push($this->nodes, $node);
   }

   public function getNode($value) {
      foreach ($this->nodes as $node) {
         if ($node->value == $value) {
            return $node;
         }
      }
      return null;
   }

   public function addEdge($value1, $value2) {
      $node1 = $this->getNode($value1);
      $node2 = $this->getNode($value2);
      $node1->addNeighbor($node2);
      $node2->addNeighbor($node1);
   }

   public function depthFirstSearch($startNode) {
      $stack = new SplStack();
      $stack->push($startNode);
      $startNode->visited = true;

      while (!$stack->isEmpty()) {
         $currentNode = $stack->pop();
         echo $currentNode->value . " ";

         foreach ($currentNode->neighbors as $neighbor) {
            if (!$neighbor->visited) {
               $stack->push($neighbor);
               $neighbor->visited = true;
            }
         }
      }
   }
}

Le constructeur initialise un tableau de nœuds vide. La méthode addNode est utilisée pour ajouter un nouveau nœud au graphique et la méthode getNode est utilisée pour obtenir l'objet nœud via la valeur du nœud.

La méthode addEdge est utilisée pour ajouter une arête entre deux nœuds. Cette arête et les autres arêtes sont bidirectionnelles. La méthode deepFirstSearch utilise une pile pour implémenter l’algorithme de recherche en profondeur d’abord. Tout d'abord, le nœud de départ est poussé sur la pile et marqué comme visité. Ensuite, le nœud actuel est extrait de la pile, la valeur du nœud est affichée et ses nœuds voisins non visités sont poussés sur la pile et marqués comme visités. Répétez ce processus jusqu'à ce que la pile soit vide.

Voici un exemple d'utilisation :

$graph = new Graph();
$graph->addNode("A");
$graph->addNode("B");
$graph->addNode("C");
$graph->addNode("D");
$graph->addNode("E");

$graph->addEdge("A", "B");
$graph->addEdge("A", "C");
$graph->addEdge("B", "D");
$graph->addEdge("C", "E");

echo "Depth First Search: ";
$graph->depthFirstSearch($graph->getNode("A"));

Le résultat est : A B D C E

Nous avons créé un graphique et ajouté des nœuds et des arêtes. Ensuite, appelez la méthode deepFirstSearch pour effectuer une recherche en profondeur d’abord, à partir du nœud « A ».

Ce qui précède est un exemple de code expliquant comment utiliser PHP pour écrire un algorithme de recherche en profondeur pour les graphiques. La recherche en profondeur est un puissant algorithme de parcours de graphes qui est très utile pour résoudre certains problèmes liés aux graphes.

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!