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 メソッドは、2 つのノード間にエッジを追加するために使用されます。このエッジと他のエッジは双方向です。 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 中国語 Web サイトの他の関連記事を参照してください。