알고리즘 - 위상 정렬(Topology Sort)

위상정렬(Topology Sort)

위상 정렬은 순서가 정해져 있는 작업을 차례대로 수행 해야될 때 순서를 결정해주기 위해 사용하는 알고리즘

위상정렬 특징

1. DAG(Directed Acyclic Graph) 에만 적용이 가능합니다.
   사이클이 발생하는 경우에는 위상 정렬을 수행할 수 없습니다.

2. 위상 정렬은 여러개의 답이 존재할 수 있습니다.

3. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단할 수 있습니다.

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

위상 정렬 알고리즘의 2가지 해결책

1. 현재 그래프는 위상 정렬이 가능한가?
2. 위상 정렬이 가능하다면 결과는 무엇인가?

위상정렬을 사용하는 방법

스택(Stack), 큐(Queue)를 사용하는 2가지 방식이 존재합니다.
그 중에서 큐를 사용하는 방식은 아래와 같습니다.

1. 진입차수가(특정한 노드로 들어오는 간선의 개수) 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2~3번 과정을 반복
   모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재
   모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과

위상 정렬 알고리즘의 성능 분석

위상 정렬 알고리즘의 시간 복잡도는 O(V+E) 입니다.

📍 참고 용어

진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수
진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수
DAG(Directed Acyclic Graph) : 싸이클이 발생하지 않는 방향의 그래프