본문 바로가기
Algorithm

Algorithm - Topological Sort(위상 정렬)

by SuldenLion 2022. 6. 12.
반응형

Topological Sort :

어떤 일을 하는 순서를 찾기 위한 알고리즘. / 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것. / '순서가 정해져 있는 작업'을 차례로 수행해야 할때, 그 순서를 결정해 주기 위해 사용하는 알고리즘. 위상 정렬은 여러 개의 답이 존재할 수 있음. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능함. -> 사이클이 발생하지 않는 방향 그래프. 사이클이 발생하는 경우 위상 정렬은 수행 불가. 

 

Topological Sort 의 특징 :

하나의 방향 그래프에는 여러 위상 정렬이 가능. / 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 함. / 위상 정렬의 과정에서 그래프에 남아있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 됨.

위상 정렬 알고리즘은 두 가지 해결책을 낸다는 특징이 있음. / 첫 번째는 현재 그래프가 위상 정렬이 가능한지, 두 번째는 위상 정렬이 가능하다면 그 결과는 무엇인지를 알아냄. / 위상 정렬을 수행하는 알고리즘은 크게 두가지인데 하나는 Stack 을 이용한 방식이고, 다른 하나는 Queue를 이용한 방식. 큐를 이용하는 방법 -> 1. 진입차수가 0인 정점을 큐에 삽입./ 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거. / 3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입. / 4. 큐가 빌때까지 2번 ~ 3번 과정을 반복. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과임.

 

위상 정렬을 이용한 기본적인 해결 방법 :

1. 진입 차수가 0인 정점(들어오는 간선의 수가 0)을 선택 - 진입 차수가 0인 정점이 여러개 존재할 경우 어느 정점을 선택해도 무방함. / 초기에 간선의 수가 0인 모든 정점을 큐에 삽입.

2. 선택된 정점과 여기에 부속된 모든 간선을 삭제 - 선택된 정점을 큐에서 삭제 / 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소.

3. 위의 과정을 반복해서 모든 정점이 선택, 삭제되면 알고리즘 종료.

 

Topological Sort와 관련된 예시

- 각각의 작업이 완료되어야만 끝나는 프로젝트.

- 선수 과목

- 큐를 이용한 위상 정렬

- 우선순위큐를 이용한 위상 정렬

- 여러 위상 순서 중 가장 짧게 걸리는 위상 정렬 구하기

 

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

반응형

댓글