위상정렬 이란?
•
정렬알고리즘의 일종이다.
•
순서가 정해진 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다.
•
사이클이 없는 방향 그래프의 모든 노드를 방향성을 모두 지키며 순서대로 나열하는 것을 의미한다.
진입차수
•
특정한 노드로 들어오는 간선의 개수를 말한다.
동작 과정
•
진입차수가 0 인 노드를 큐에 담는다.
•
노드를 꺼내 해당 노드에서 출발하는 모든 간선을 그래프에서 제거한다.
◦
진입차수 테이블을 갱신한다.
•
진입차수의 값이 0 인 노드를 큐에 담는다.
•
이를 큐가 빌 때 까지 반복한다.