[Algorithm] 위상 정렬 - Topology Sort (파이썬, C++)

위상 정렬 - Topology Sort

위상 정렬은 순서가 정해져 있는 노드들을 차례대로 정렬할 때 사용할 수 있는 알고리즘이다. 더 개념적으로 정의하자면, 위상 정렬이란 "방향 그래프의 모든 노드를 방향성에 따라 정렬"하는 것이다.

 

위상 정렬에서 그래프는 방향 그래프이므로 각 방향에 대한 간선이 존재한다. 이때 어떤 노드가 다른 노드를 가리킬 때, 들어오는 간선의 개수를 "진입 차수"라 한다.

 

 

위상 정렬 알고리즘

① 진입 차수가 0인 노드를 큐에 넣는다.

② 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

③ 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다.

④ 큐가 빌 때까지 ②,③ 과정을 반복한다.

 

 

파이썬 소스 코드)

 

C++ 소스 코드)

 

 

위상 정렬의 시간 복잡도

위상 정렬을 수행할 때는 차례대로 모든 노드를 확인하면서, 해당 노드에서 출발하는 간선을 차례대로 제거한다. 그렇기 때문에 시간 복잡도는 O(v + e)가 된다.

 

 

한계

위의 위상 정렬 알고리즘은 입력에서 사이클이 없다는 전제하에 짠 알고리즘임을 명심하자. 만약 사이클이 존재할 경우, 큐에서 원소가 v번 추출되기 전에 큐가 비어 버릴 것이다. 사이클이 포함되어 있는 원소 중에서 어떠한 원소도 큐에 못 들어가기 때문이다. 따라서 이에 대한 처리를 해주려면 반복문에 while 대신 for문으로 v만큼 반복하면서 큐가 빌 경우 break문을 걸어주어 처리한다.

 

 

 

⊙해당 문서는 "이것이 취업을 위한 코딩테스트다 - 나동빈 저"의 책을 공부하며 정리한 글입니다.

book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬