위상정렬

 ( 참고 강의 : https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=9&t=1986s&ab_channel=%EB%8F%99%EB%B9%88%EB%82%98 )

 : 위상 정렬

     : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것.
     

     위와 같이 표현되고, 고급 알고리즘은 자료구조와, 알고리즘 모두 충족해야 가능하다.

     
     용어로는
     진입차수 ( Indegree ) : 특정한 노드로 들어오는 간선의 개수
     진출차수 ( Outdegerr ) : 특정한 노드에서 나가는 간선의 개수
     를 알아두자.

     위상 정렬 알고리즘은 큐를 이용해서도 구현할 수 있는데,
     1. 진입차수가 0인 모든 노드를 큐에 넣는다.
     2. 큐가 빌 때까지 다음의 과정을 반복한다.
        1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다.
        2) 새롭게 진입차수가 0이된 노드를 큐에 넣는다.

     결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과와 같다.

     만약, 사이클이 있다면 모든 노드의 진입차수가 0보다 크므로 애초에 수행할 수 없다.

 

     그림을 보면 이해가 정말 빠르게 될 수 있다.

     최종적으로, 큐에 들어간 순서대로 위상 정렬을 할 수 있으며,
     여러가지 답이 존재할 수 있다. 

      : 한 단계에서 큐에 새롭게 들어가는 원소가 2개 이상인 경우가 있다면, 여러가지 답이 존재한다.

     모든 원소를 방문하기전에 큐가 빈다면, 사이클이 존재한다고 판단할 수 있다.
      : 사이클에 포함된 원소 중에서 어떠한 원소도 큐에 들어가지 못하는 경우가 있다.

     스택을 활용한 DFS를 이용해 위상 정렬을 수행할 수도 있다.