위상 정렬(사용하는 이유, 특징, 구현, 시간 복잡도)

사용하는 이유

주어진 그래프에서의 진입차수를 이용한 순서를 구하기 위하여

 

특징

여러가지 위상 정렬 그래프가 나올 수 있다.

 

구현

위상 정렬을 정렬한 리스트와

진입 차수가 0이 되면 삽입할 큐 2개를 이용하여 구현다

현재 노드와 연결된 간선을 하나하나 제거해주면 진입되는 노드의 진입 차수가 0이 되면 큐에 넣으면서 정렬할 수 있도록 한다.

 

시간 복잡도

시간 복잡도는 O(V+E) 모든 노드에 대해 모든 간선을 탐색하여야 한다.