So schreiben Sie mit PHP einen Tiefensuchalgorithmus für Diagramme

So schreiben Sie mit PHP einen Tiefensuchalgorithmus für einen Graphen

Die Tiefensuche (DFS) ist ein Graph-Traversal-Algorithmus, der einen Zweig im Graphen so tief wie möglich untersucht, bis eine Fortsetzung nicht mehr möglich ist. Kehren Sie dann zum vorherigen Knoten zurück und erkunden Sie weitere Zweige, bis alle Knoten besucht wurden. In diesem Artikel lernen wir, wie man mit PHP einen Tiefensuchalgorithmus für Diagramme schreibt.

Zuerst erstellen wir eine Knotenklasse, um die Knoten im Diagramm darzustellen:

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);
   }
}

Jeder Knoten hat einen Wert, ein besuchtes Tag und ein Array von Nachbarn. Im Konstruktor initialisieren wir diese Eigenschaften.

Als nächstes erstellen wir eine Diagrammklasse und implementieren den Tiefensuchalgorithmus:

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;
            }
         }
      }
   }
}

Der Konstruktor initialisiert ein leeres Knotenarray. Die Methode addNode wird verwendet, um dem Diagramm einen neuen Knoten hinzuzufügen, und die Methode getNode wird verwendet, um das Knotenobjekt über den Knotenwert abzurufen.

Die addEdge-Methode wird verwendet, um eine Kante zwischen zwei Knoten hinzuzufügen. Diese Kante und andere Kanten sind bidirektional. Die Methode DepthFirstSearch verwendet einen Stapel, um den Tiefensuchalgorithmus zu implementieren. Zunächst wird der Startknoten auf den Stapel geschoben und als besucht markiert. Dann wird der aktuelle Knoten vom Stapel entfernt, der Wert des Knotens wird ausgegeben und seine nicht besuchten Nachbarknoten werden auf den Stapel verschoben und als besucht markiert. Wiederholen Sie diesen Vorgang, bis der Stapel leer ist.

Hier ist ein Anwendungsbeispiel:

$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"));

Die Ausgabe ist: A B D C E

Wir haben ein Diagramm erstellt und einige Knoten und Kanten hinzugefügt. Rufen Sie dann die Methode DepthFirstSearch auf, um eine Tiefensuche ausgehend vom Knoten „A“ durchzuführen.

Das Obige ist der Beispielcode für die Verwendung von PHP zum Schreiben eines Tiefensuchalgorithmus für Diagramme. Die Tiefensuche ist ein leistungsstarker Graph-Traversal-Algorithmus, der für die Lösung einiger graphbezogener Probleme sehr nützlich ist.

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