如何使用PHP編寫圖的深度優先搜尋演算法

如何使用PHP編寫圖的深度優先搜尋演算法

深度優先搜尋（DFS）是一種圖遍歷演算法，它透過沿著圖中某個分支盡可能深地探索，直到無法繼續為止。然後回溯到上一個節點繼續探索其他分支，直到所有節點都被存取。在本文中，我們將學習如何使用PHP編寫圖的深度優先搜尋演算法。

首先，我們建立一個節點類別來表示圖中的節點：

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

每個節點具有一個值，一個已存取標記和一個鄰居陣列。在建構函式中，我們初始化這些屬性。

接下來，我們建立一個圖類別並實作深度優先搜尋演算法：

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

建構函式初始化一個空節點陣列。 addNode方法用於新增一個節點到圖中，getNode方法用於透過節點值取得節點物件。

addEdge方法用來新增兩個節點之間的邊，該邊和其它邊都是雙向的。 depthFirstSearch方法使用堆疊來實作深度優先搜尋演算法。首先，將起始節點壓入堆疊中，並標記為已存取。然後，從堆疊中彈出目前節點，輸出節點的值，並將其未存取的鄰居節點壓入堆疊中，並標記為已存取。重複這個過程，直到堆疊為空。

下面是一個使用範例：

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

輸出結果為：A B D C E

我們建立了一個圖，並加入了一些節點和邊。然後，呼叫depthFirstSearch方法進行深度優先搜索，並從節點"A"開始。

以上就是如何使用PHP寫圖的深度優先搜尋演算法的範例程式碼。深度優先搜尋是一種強大的圖遍歷演算法，對於解決一些與圖相關的問題非常有用。

以上是如何使用PHP編寫圖的深度優先搜尋演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！