Maison > développement back-end > tutoriel php > Comment écrire un algorithme de recherche en profondeur pour les graphiques en utilisant PHP

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

WBOY
Libérer: 2023-07-09 20:46:01
original
1009 Les gens l'ont consulté

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);
   }
}
Copier après la connexion

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;
            }
         }
      }
   }
}
Copier après la connexion

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"));
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal