[알고리즘 개념정리] 위상정렬

주요 개념

사이클이 없는 방향 그래프(DAG)로 풀이 가능

위상정렬: 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것
노드를 하나씩 나열하되 방향성에 거스르지 않도록 나열해야됨

큐를 이용하거나 dfs를 이용해서 풀이 가능

• 순환하지 않는(사이클이 없는) 방향 그래프에 대해서만 수행 가능
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재함
  (사이클을 이루고 있는 원소는 진입차수가 0이 될 수 없어 큐에 들어가지 못하기 때문)
• 답이 여러개 나올 수 있음

시간복잡도: O(V+E)

진입차수: 특정한 노드로 들어오는 간선의 개수
진출자수: 특정한 노드에서 나가는 간선의 개수

동작원리

1. 진입차수가 0인 모든 노드를 큐에 삽입

2. 큐가 빌 때까지 아래 반복
   1) 큐에서 원소를 꺼내 해당 원소(정점)에서 나가는 간선 하나만 그래프에서 제거

   큐에서 꺼낸 정점: 2번, 2번 -> 3번 으로 연결된 상황이라면 이 간선을 제거
   -> 2번과 연결된 간선을 찾은 뒤 (2번이 start인 정점으로서 연결된 정점, 여기서는 3번)
   -> 3번의 진입차수를 1 감소시킴
   

   2) 새롭게 진입차수가 0이 된 노드를 큐에 넣음

-> 각 노드가 큐에 들어온 순서가 곧 위상정렬을 수행한 결과임이라고 나와있는데 소스코드나 다른 블로그 보면 큐에서 pop된 순서가 맞는듯

큐에 삽입된 노드 순서가 위상 정렬의 결과임

1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7

소스코드

참고: 동빈나 이코테 영상
https://www.youtube.com/watch?v=aOhhNFTIeFI&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=8