위상 정렬 (Topology Sort)

※ 위상 정렬 (Topology Sort): 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 (큐 자료구조 사용)

 

 • indegree(진입 차수): 특정한 노드로 들어오는 간선의 개수

 

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

② 큐가 빌 때까지 다음의 과정을 반복한다.

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

  Ⅱ. 새롭게 진입차수가 0이 된 노드를 큐에 삽입

  ⁎ 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것!

 

위상 정렬 수행 결과 => 큐에서 빠져나간 노드들을 순서대로 출력 

 

 

출처| 이것이 취업을 위한 코딩테스트다 with 파이썬(나동빈 저)