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 메소드는 두 노드 사이에 가장자리를 추가하는 데 사용됩니다. 이 가장자리와 다른 가장자리는 양방향입니다. deepFirstSearch 메서드는 스택을 사용하여 깊이 우선 검색 알고리즘을 구현합니다. 먼저, 시작 노드가 스택에 푸시되고 방문한 것으로 표시됩니다. 그런 다음 현재 노드가 스택에서 팝되고 노드의 값이 출력되며 방문하지 않은 이웃 노드가 스택에 푸시되고 방문한 것으로 표시됩니다. 스택이 빌 때까지 이 과정을 반복합니다.

사용 예는 다음과 같습니다.

$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

그래프를 만들고 일부 노드와 간선을 추가했습니다. 그런 다음, node "A"부터 시작하여 깊이 우선 검색을 수행하기 위해 deepFirstSearch 메서드를 호출합니다.

위는 PHP를 사용하여 그래프에 대한 깊이 우선 검색 알고리즘을 작성하는 방법에 대한 샘플 코드입니다. 깊이 우선 검색은 일부 그래프 관련 문제를 해결하는 데 매우 유용한 강력한 그래프 순회 알고리즘입니다.

위 내용은 PHP를 사용하여 그래프에 대한 깊이 우선 검색 알고리즘을 작성하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!