의존 조건을 지킨 나열
A→C, B→C라는 조건만 있으면 A,B,C와 B,A,C는 모두 가능하다. A와 B 사이에 선후 관계가 지정되지 않았기 때문이다. 정점 이름의 크기순으로 나열하는 일반 정렬과는 목적이 다르다.
진입차수가 0인 정점
들어오는 간선이 없는 정점을 하나 골라 결과에 넣고 그 정점과 나가는 간선을 제거하는 과정을 반복할 수 있다. 제거로 인해 새롭게 진입차수가 0이 되는 정점들을 이어 처리한다.
순환이 있을 때
아직 정점이 남았는데 진입차수가 0인 정점을 더 찾지 못하면 유향 순환이 있는 경우를 의심할 수 있다. 순환 그래프의 정점 일부만 출력한 결과를 전체의 올바른 위상 정렬로 취급해서는 안 된다.
구현과 유일성
인접 리스트와 진입차수를 사용하면 각 정점과 간선을 처리하는 기본 방식은 O(V+E)에 구현할 수 있다. 동시에 고를 수 있는 정점이 여러 개라면 선택 규칙에 따라 유효한 나열이 달라질 수 있다.
관련 문서
비순환 유향 그래프 / 유향 그래프 / 그래프의 차수 / 너비 우선 탐색 / 깊이 우선 탐색 / 시간 복잡도 / 정점 (그래프 이론)