Bagaimana untuk menulis algoritma carian mendalam-pertama untuk graf menggunakan PHP

Cara menulis algoritma carian depth-first untuk graf menggunakan PHP

Depth-first search (DFS) ialah algoritma traversal graf yang meneroka sedalam mungkin di sepanjang cawangan dalam graf sehingga ia tidak lagi dapat diteruskan. Kemudian undur ke nod sebelumnya dan teruskan meneroka cawangan lain sehingga semua nod telah dilawati. Dalam artikel ini, kita akan belajar cara menulis algoritma carian mendalam-pertama untuk graf menggunakan PHP.

Pertama, kami mencipta kelas nod untuk mewakili nod dalam graf:

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

Setiap nod mempunyai nilai, teg yang dilawati dan tatasusunan jiran. Dalam pembina, kami memulakan sifat ini.

Seterusnya, kami mencipta kelas graf dan melaksanakan algoritma carian kedalaman pertama:

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

Pembina memulakan tatasusunan nod kosong. Kaedah addNode digunakan untuk menambah nod baharu pada graf, dan kaedah getNode digunakan untuk mendapatkan objek nod melalui nilai nod.

Kaedah addEdge digunakan untuk menambah tepi antara dua nod Tepi ini dan tepi lain adalah dua arah. Kaedah depthFirstSearch menggunakan tindanan untuk melaksanakan algoritma carian depth-first. Mula-mula, nod permulaan ditolak ke tindanan dan ditandakan sebagai dilawati. Kemudian, nod semasa muncul dari tindanan, nilai nod adalah output, dan nod jiran yang tidak dilawati ditolak ke tindanan dan ditandakan sebagai dilawati. Ulangi proses ini sehingga timbunan kosong.

Berikut ialah contoh penggunaan:

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

Outputnya ialah: A B D C E

Kami mencipta graf dan menambah beberapa nod dan tepi. Kemudian, panggil kaedah depthFirstSearch untuk melakukan carian depth-first, bermula dari nod "A".

Di atas ialah contoh kod cara menggunakan PHP untuk menulis algoritma carian pertama mendalam untuk graf. Carian depth-first ialah algoritma traversal graf yang berkuasa yang sangat berguna untuk menyelesaikan beberapa masalah berkaitan graf.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma carian mendalam-pertama untuk graf menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!