위상 정렬은 어떻게 정렬되나요?

방법: 1. 그래프에서 내차수가 0인 노드를 찾아 그래프에서 이 노드를 제거하고 시퀀스 E에 추가합니다. 2. 그래프에서 1에서 찾은 노드와 관련된 모든 가장자리를 제거합니다. 제거 3. 그래프의 모든 노드가 제거되거나 진입차수가 0인 노드를 찾을 수 없을 때까지 1단계와 2단계를 반복합니다.

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

1. 차수가 0인 그래프에서 노드를 찾아 그래프에서 이 노드를 제거한 후 시퀀스 E

2. 그래프에서 1에서 찾은 노드의 관련 가장자리를 모두 제거합니다.

3. 그래프의 모든 노드가 제거되거나 차수가 0인 노드를 찾을 수 없을 때까지 1과 2를 반복합니다.

이때 그래프의 노드 수가 0이면 토폴로지 순서는 이 발견되면 그래프의 노드 수가 0이 아닌 경우 그래프에 순환이 있으며 위상 정렬을 수행할 수 없음을 의미합니다.

확장 정보:

방향성 비순환 그래프(줄여서 DAG)에서 위상 정렬을 수행하려면 G의 모든 정점을 그래프의 정점 u와 v 쌍이 다음과 같은 선형 시퀀스로 배열하는 것입니다. edge ∈E(G)이면 선형 시퀀스에서 u가 v 앞에 나타납니다. 일반적으로 이러한 선형 수열을 위상수열(topological order)을 만족하는 수열, 줄여서 위상수열(topological 수열)이라고 합니다. 간단히 말해서, 집합의 부분 순서에서 집합의 전체 순서까지 이 작업을 위상 정렬이라고 합니다.

실행 단계

AOV 네트워크에서 위상 순서를 구성하는 위상 정렬 알고리즘은 주로 in-degree가 0인 정점이 없을 때까지 루프에서 다음 두 단계를 수행합니다.

(1) 차수가 0인 꼭지점을 선택하고 출력합니다.

(2) 이 꼭지점과 모든 나가는 가장자리를 네트워크에서 삭제합니다.

루프가 끝난 후 출력 정점 수가 네트워크의 정점 수보다 적으면 "루프" 정보가 출력되고, 그렇지 않으면 출력 정점 시퀀스는 위상 시퀀스입니다.

더 많은 컴퓨터 관련 지식을 알고 싶다면 FAQ 칼럼을 방문해주세요!

위 내용은 위상 정렬은 어떻게 정렬되나요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!