위상 정렬

개념

위상 정렬(Topology Sort)는 순서가 정해져있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해서 사용하는 알고리즘이다. 쉽게 말하면 그래프의 흐름이 있고, 다양한 조건이 얽혀있을 때 정확히 1열로 그래프의 노드를 나열할 수 있도록 하는 알고리즘이 위상 정렬인 것이다.

 

따라서 다음과 같이 모든 조건을 만족하도록 일직선의 순서를 하나 만들어낼 수 있는 것이다.

대학생 되기 -> 학과 사이트 가입하기 -> 4학년 되기 -> 정보처리기사 합격하기 -> 자격 서류 제출하기 -> 졸업시험 신청하기 -> 졸업하기

이렇게 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '졸업하기'까지 갈 수 있다. 또한 위 말고도 다른 답도 존재하게 된다. 그래서 위상 정렬은 여러 개의 답이 존재할 수 있고, 이 점이 또 다른 매력점으로 다가오게 된다.

 

또한 위상 정렬은 Directed Acyclic Graph에만 적용이 가능하다. 이 것은 사이클이 발생하지 않는 방향 그래프이다. 즉, 사이클이 발생하는 경우는 위상 정렬을 수행할 수 없다. 왜냐하면, 위상 정렬은 시작점이 존재해야 하는 알고리즘인데, 사이클이 생겨버리면 시작점을 찾을 수가 없게 되어버리기 때문이다.

 

따라서 위상 정렬 알고리즘은 2가지 해결책을 낸다는 특징을 가지고 있다. 

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

이러한 위상 정렬을 수행하는 알고리즘으로는 크게 2가지가 존재한다. 하나는 스택이고, 하나는 큐이다.

 

그럼 여기서는 큐를 이용한 방법을 소개한다.

1. 먼저 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내서 연결된 모든 간선을 제거한다.
3. 간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입한다.
4. 큐가 빌 때까지 2~3번 과정을 반복한다.

 

즉, 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.

 

그럼 이제 위상 정렬을 수행하는 알고리즘을 수행해보자.

결과적으로 위와 같이 위상 정렬의 정답은 큐에서 꺼낸 순서가 된다. 다만 위상 정렬은 결과가 여러 가지가 있을 수 있으므로, 이는 그 중 한가지라고 보면 된다.

 

그리고 위상 정렬은 정점의 개수 + 간선의 개수만큼 소요되므로 매우 빠른 알고리즘 중 하나이다. 정리하면, 위상 정렬의 시간 복잡도는 O(V + E)이다.

 

구현

위상 정렬은 순서가 정해져있는 작업이 여러 개 나열이 되어있을 때, 이들의 순서를 정확히 결정해주는 알고리즘이다.