PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법
위상 정렬은 방향성 비순환 그래프(DAG)를 정렬하는 알고리즘입니다. 그 원리는 정렬 결과의 모든 모서리 방향이 일관되도록 하기 위해 종속성에 따라 그래프의 노드를 정렬하는 것입니다. 실제 개발에서는 작업 스케줄링, 종속성 분석 등의 문제를 해결하기 위해 위상 정렬을 사용하는 경우가 많습니다. 이 기사에서는 코드 예제와 함께 PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법을 소개합니다.
알고리즘 아이디어:
- 각 노드의 내차를 저장하기 위한 내차 배열 생성(즉, 이 노드를 가리키는 노드 수)
- 정렬 결과를 저장하는 결과 배열 생성; 트래버스 그래프의 노드에 대해 각 노드의 내부 차수를 계산하고 이를 내부 차수 배열에 저장합니다.
- 큐를 초기화하고 내부 차수가 0인 모든 노드를 대기열에 추가합니다. 대기열이 비어 있지 않으면 대기열에서 노드를 순차적으로 제거하고 결과 배열에 추가합니다.
- 노드의 이웃 노드를 탐색하고 각 이웃 노드의 내부 차수를 1만큼 줄입니다. 이웃 노드가 0으로 감소한 다음 대기열에 넣습니다.
- 큐가 빌 때까지 5~7단계를 반복합니다.
- 결과 배열의 노드 수가 그래프의 노드 수와 같으면 정렬은 다음과 같습니다. 그렇지 않으면 그래프에 주기가 있어 위상 정렬을 수행할 수 없습니다.
- 다음은 위의 아이디어를 바탕으로 작성된 PHP 위상 정렬 알고리즘의 코드 예제입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | <?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 ]++;
}
}
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 "图中存在环,无法进行拓扑排序。
";
}
?>
|
로그인 후 복사
위 코드에서 - 배열에. 코드를 실행하면 위상 정렬 결과가 출력됩니다.
요약:
이 기사에서는 PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법을 소개하고 해당 코드 예제를 제공합니다. 위상 정렬은 작업 스케줄링과 같은 문제를 해결하는 데 자주 사용되는 실용적인 알고리즘입니다. 토폴로지 정렬 알고리즘을 익히면 방향성 비순환 그래프의 처리 기능이 향상되고 개발 중에 다양한 종속성 분석을 지원하는 데 도움이 됩니다. 이 기사가 도움이 되기를 바랍니다.
위 내용은 PHP를 사용하여 위상 정렬 알고리즘을 작성하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!