0. 위상 정렬(Topological Sort)
위상 정렬은 유향 그래프의 정점들을 나열하는 것을 의미한다.
순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘으로 위상 정렬의 결과는 여러 개일 수 있다.
가장 잘 설명되는 예시로는 선수과목(prerequisite) 구조이다. 만약 특정 수강 과목에 선수 과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 수강 순서를 찾아낼 수 있다.
위상 정렬이 성립하기 위해서는 그래프의 순환이 존재하지 않는 비순환 유향 그래프(directed acyclic pragh)여야 한다.
위상 정렬은 아래 2가지에 대한 판단이 가능하다.
- 현재 그래프는 위상 정렬이 가능한지 → 사이클이 존재하지 않는지
- 위상 정렬이 존재한다면 그 결과는 무엇인지
1. 알고리즘
위상 정렬은 BFS와 DFS로 모두 구현이 가능하다.
이번에는 큐를 이용한 BFS로 구현할 예정이다.
- 진입 차수가 0인 정점을 큐에 모두 넣는다.
- 큐에서 진입 차수가 0인 정점을 꺼내어 자신과 인접한 정점의 간선을 제거한다. → 인접한 정점의 진입 차수를 1 감소시킨다.
- 큐가 공백이 될 때까지 1번부터 작업을 반복한다.
- 모든 노드가 다 처리되었다면 위상 정렬 완성, 처리되지 않은 노드가 있다면 사이클 발생
2. 구현
2-1. 위상 정렬이 가능한 경우
2-2. 위상 정렬이 불가능한 경우(사이클이 발생한 경우)
반응형