[알고리즘] 위상 정렬

위상 정렬(Topological Sort)

순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않고 모든 정점을 나열하는 것

나동빈 블로그

 

특징

- 하나의 방향 그래프에서 여러 위상 정렬이 가능
ex 1) 대학생되기 → 4학년 되기 → 정보처리기사 합격하기 → 자격서류 제출하기 → 졸업시험 신청 → 졸업하기
    2) 대학생되기 → 학과사이트 가입하기 → 졸업시험 신청하기 → 졸업하기

- DAG에만 적용이 가능 ▶ 사이클이 발생하는 경우 위상 정렬 수행 불가
DAG란? 2021.07.07 - [IT/CS] - [알고리즘] 방향 비순환 그래프

[알고리즘] 방향 비순환 그래프

- 위상 정렬을 통해 1️⃣ 현재 그래프의 위상 정렬 가능 여부 2️⃣ 위상 정렬이 가능 시 결과를 알 수 있음

- 위상 정렬 과정 중, 그래프에 남아 있는 정점 중 진입 차수가 0인 정점이 없다면 위상 정렬 알고리즘은 중단됨

 

방법

1. 진입 차수가 0인 모든 정점을 Queue에 삽입

2. 선택된 정점과 관련된 간선 삭제
- 선택된 정점을 큐에서 삭제
- 선택된 정점에 부속된 모든 간서에 대해 간선 수 감소

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

 

출처 https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html