PHP 알고리즘 설계 아이디어: 위상 정렬 문제에 대한 효율적인 솔루션을 얻는 방법은 무엇입니까?

PHP 알고리즘 설계 아이디어: 위상 정렬 문제에 대한 효율적인 솔루션을 얻는 방법은 무엇입니까?

토폴로지 정렬은 그래프 이론의 고전적인 문제입니다. 주요 목표는 그래프의 모든 정점이 진입 차수보다 작거나 같다는 조건을 충족하도록 방향성 비순환 그래프(DAG)를 정렬하는 것입니다. . 토폴로지 정렬은 작업 스케줄링, 컴파일러 설계 등과 같은 많은 시나리오에서 널리 사용됩니다.

이 기사에서는 PHP 언어를 사용하여 위상 정렬을 구현하는 효율적인 솔루션을 소개합니다. 먼저 위상 정렬 알고리즘의 기본 원리를 논의한 다음 구체적인 코드 예제를 제공합니다.

1. 위상 정렬 알고리즘의 원리

위상 정렬 알고리즘은 주로 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)의 아이디어를 기반으로 합니다. 구체적으로 토폴로지 정렬 알고리즘에는 다음 단계가 포함됩니다.

a) 먼저 방향성 그래프의 인접 목록 표현을 구성해야 합니다. 여기서 각 정점은 배열의 인덱스 역할을 하고 정점이 가리키는 정점은 배열의 값으로.

b) 그런 다음 그래프에서 차수가 0인 정점을 시작 정점으로 선택하고 이를 대기열에 추가합니다.

c) 다음으로 큐의 정점을 반복하고 인접한 정점의 차수를 1만큼 줄입니다. 인접한 정점의 진입차수가 0이면 대기열에 추가합니다.

d) 대기열이 빌 때까지 위 과정을 반복합니다. 마지막으로, 획득된 큐의 정점은 위상 정렬의 결과입니다.

2. 위상 정렬 알고리즘 코드 구현

다음은 PHP 언어를 사용하여 위상 정렬 알고리즘을 구현하는 코드 예제입니다.

class Graph {
    private $adjList;

    public function __construct() {
        $this->adjList = [];
    }

    public function addEdge($src, $dest) {
        if (!isset($this->adjList[$src])) {
            $this->adjList[$src] = [];
        }
        $this->adjList[$src][] = $dest;
    }

    public function topologicalSort() {
        $inDegree = [];
        foreach ($this->adjList as $src => $destList) {
            $inDegree[$src] = 0;
        }

        foreach ($this->adjList as $src => $destList) {
            foreach ($destList as $dest) {
                $inDegree[$dest]++;
            }
        }

        $queue = new SplQueue();
        foreach ($inDegree as $src => $in) {
            if ($in == 0) {
                $queue->enqueue($src);
            }
        }

        $result = [];

        while (!$queue->isEmpty()) {
            $src = $queue->dequeue();
            $result[] = $src;

            if (isset($this->adjList[$src])) {
                foreach ($this->adjList[$src] as $dest) {
                    $inDegree[$dest]--;
                    if ($inDegree[$dest] == 0) {
                        $queue->enqueue($dest);
                    }
                }
            }
        }

        return $result;
    }
}

$g = new Graph();
$g->addEdge(1, 3);
$g->addEdge(1, 4);
$g->addEdge(2, 4);
$g->addEdge(3, 5);
$g->addEdge(4, 5);

$result = $g->topologicalSort();

foreach ($result as $vertex) {
    echo $vertex . ' ';
}

위 코드에서는 생성자와 addEdge 메서드를 포함하는 Graph 클래스가 먼저 정의됩니다. 모서리를 추가하고 위상 정렬 방법인 topologicalSort를 사용합니다. main 함수에서는 방향성 그래프를 생성하고 위상 정렬(topological sorting)을 수행한 후 최종적으로 위상 정렬(topological sorting)에 따른 결과를 출력한다.

요약:

위상 정렬 알고리즘의 원리와 구체적인 구현을 설명하고 이를 코드 예제와 결합하여 PHP 언어로 효율적인 솔루션을 구현합니다. 토폴로지 정렬은 많은 실제 응용 프로그램에서 중요한 역할을 할 수 있으며 다양한 작업 예약 및 종속성 문제를 해결하는 데 도움이 됩니다.

위 내용은 PHP 알고리즘 설계 아이디어: 위상 정렬 문제에 대한 효율적인 솔루션을 얻는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!