PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법

PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법

위상 정렬은 방향성 비순환 그래프(DAG)를 정렬하는 알고리즘입니다. 그 원리는 정렬 결과의 모든 모서리 방향이 일관되도록 하기 위해 종속성에 따라 그래프의 노드를 정렬하는 것입니다. 실제 개발에서는 작업 스케줄링, 종속성 분석 등의 문제를 해결하기 위해 위상 정렬을 사용하는 경우가 많습니다. 이 기사에서는 코드 예제와 함께 PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법을 소개합니다.

알고리즘 아이디어:

1. 각 노드의 내차를 저장하기 위한 내차 배열 생성(즉, 이 노드를 가리키는 노드 수)
2. 정렬 결과를 저장하는 결과 배열 생성; 트래버스 그래프의 노드에 대해 각 노드의 내부 차수를 계산하고 이를 내부 차수 배열에 저장합니다.
3. 큐를 초기화하고 내부 차수가 0인 모든 노드를 대기열에 추가합니다. 대기열이 비어 있지 않으면 대기열에서 노드를 순차적으로 제거하고 결과 배열에 추가합니다.
4. 노드의 이웃 노드를 탐색하고 각 이웃 노드의 내부 차수를 1만큼 줄입니다. 이웃 노드가 0으로 감소한 다음 대기열에 넣습니다.
5. 큐가 빌 때까지 5~7단계를 반복합니다.
6. 결과 배열의 노드 수가 그래프의 노드 수와 같으면 정렬은 다음과 같습니다. 그렇지 않으면 그래프에 주기가 있어 위상 정렬을 수행할 수 없습니다.
7. 다음은 위의 아이디어를 바탕으로 작성된 PHP 위상 정렬 알고리즘의 코드 예제입니다.

8. <?php
   
   function topologicalSort($graph) {
       $inDegree = []; // 入度数组
       $result = []; // 排序结果
       $queue = new SplQueue(); // 队列
   
       // 初始化入度数组
       foreach ($graph as $node => $neighbors) {
           $inDegree[$node] = 0;
       }
   
       // 计算入度数组
       foreach ($graph as $node => $neighbors) {
           foreach ($neighbors as $neighbor) {
               $inDegree[$neighbor]++;
           }
       }
   
       // 将入度为0的节点入队
       foreach ($inDegree as $node => $degree) {
           if ($degree == 0) {
               $queue->enqueue($node);
           }
       }
   
       // 队列不为空时
       while (!$queue->isEmpty()) {
           $node = $queue->dequeue();
           $result[] = $node;
   
           // 遍历邻居节点
           foreach ($graph[$node] as $neighbor) {
               $inDegree[$neighbor]--;
               if ($inDegree[$neighbor] == 0) {
                   $queue->enqueue($neighbor);
               }
           }
       }
   
       // 判断是否成功排序
       if (count($result) == count($graph)) {
           return $result;
       } else {
           return false;
       }
   }
   
   // 测试用例
   $graph = [
       'A' => ['B', 'C'],
       'B' => ['C', 'D'],
       'C' => ['E'],
       'D' => ['F'],
       'E' => [],
       'F' => ['G'],
       'G' => []
   ];
   
   $result = topologicalSort($graph);
   if ($result) {
       echo "拓扑排序结果: " . implode(' -> ', $result) . "
   ";
   } else {
       echo "图中存在环，无法进行拓扑排序。
   ";
   }
   
   ?>

위 코드에서
9. 배열에. 코드를 실행하면 위상 정렬 결과가 출력됩니다.

요약:

이 기사에서는 PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법을 소개하고 해당 코드 예제를 제공합니다. 위상 정렬은 작업 스케줄링과 같은 문제를 해결하는 데 자주 사용되는 실용적인 알고리즘입니다. 토폴로지 정렬 알고리즘을 익히면 방향성 비순환 그래프의 처리 기능이 향상되고 개발 중에 다양한 종속성 분석을 지원하는 데 도움이 됩니다. 이 기사가 도움이 되기를 바랍니다.

위 내용은 PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!