•
개념
◦
위상 정렬은 비순환 방향 그래프(DAG)에서 정점들을 선형으로 정렬하는 것이다.
▪
모든 간선 (u, v)에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬된다.
▪
그래프가 비순환 방향 그래프가 아닌 경우, 그래프에 대한 위상 정렬은 불가능하다.
•
그래프에 사이클이 존재하면서 두 정점 u, v가 사이클에 속한 정점일 경우, 정점 u가 v보다 먼저 오거나 v가 u보다 먼저 올 수 있기 때문이다.
•
구현에서 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단할 수 있다.
◦
사이클에 포함된 원소 중에서 해당되는 어떠한 원소도 큐에 들어가지 못하게 되기 때문이다.
◦
하나의 DAG에서 하나 이상의 위상 순서가 나올 수 있으며 모든 간선은 오른쪽 방향만 가리키게 된다.
•
구현
1.
모든 정점의 진입차수를 설정한다.
2.
진입차수가 0인 정점을 방문한 것으로 표시하고 큐에 정점을 추가한다.
3.
큐가 비어있게 될 때까지 순회하며 다음 작업을 수행한다.
a.
큐에서 값을 꺼내 해당 노드에서 나가는 방향을 그래프에서 제거한다.
•
해당 간선의 도착 노드의 진입차수가 1씩 감소한다
b.
진입차수가 0인 노드를 큐에 삽입한다.
