> 백엔드 개발 > PHP 튜토리얼 > PHP를 사용하여 그래프에 대한 깊이 우선 검색 알고리즘을 작성하는 방법

PHP를 사용하여 그래프에 대한 깊이 우선 검색 알고리즘을 작성하는 방법

WBOY
풀어 주다: 2023-07-09 20:46:01
원래의
1032명이 탐색했습니다.

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿