[알고리즘] 15. 위상 정렬

1. 위상 정렬 (Topological Sort)

• 작업의 순서가 정해져 있을 때, 그 순서를 결정하는 알고리즘

• 여러 공정으로 이루어진 작업을 모델링하는 데 사용

• 처리해야 할 여러 작업이 있으며, 이들 사이의 선후 관계가 있을 경우 방향 그래프로 표현 가능

- 정점: 해야 할 일

- 간선: 작업 간의 선후 관계

• 방향 그래프에서 각 정점의 선행 순서를 유지하면서 모든 정점을 나열하는 과정

• 사이클이 존재하면 위상 정렬을 수행할 수 없음

 

(예시)

• 대학의 선수 과목 구조

- 특정 과목을 수강하려면 선수 과목을 먼저 들어야 함

- 위상 정렬을 통해 올바른 수강 순서를 결정 가능

 

• 일정 및 업무 스케줄링

- 선행 작업을 먼저 수행해야 하는 경우 활용 가능

 

 

2. DAG (Directed Acyclic Graph)

• 위상 정렬은 DAG(비순환 방향 그래프)에 대해서만 적용 가능

 

DAG의 특징

• 방향 그래프이면서 사이클이 없는 그래프

• 여러 공정으로 이루어진 작업을 모델링하는 데 유용

• 사이클이 존재하면 위상 정렬 수행 불가

• DAG의 방향 간선을 한 방향으로 정렬하는 것이 위상 정렬의 목표

 

 

3. 위상 정렬 알고리즘

위상 정렬을 수행하는 과정

(1) 진입 차수가 0인 정점을 선택

(2) 선택한 정점과 연결된 모든 간선을 제거

(3) 모든 정점이 제거될 때까지 반복

(4) 제거된 정점의 순서가 위상 순서 (Topological Order)

 

• 정점 선택 과정에서 진입 차수가 0인 정점이 없으면 위상 정렬 실패

• 방향 그래프의 구조에 따라 여러 가지 위상 정렬 결과가 존재할 수 있음

• 그래프에 사이클이 존재하면 위상 정렬 불가능

 

(성질)

• 간선 (i, j)가 존재하면 위상 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 위치해야 함

• 사이클이 존재하면 이 성질을 만족할 수 없어 위상 정렬이 불가능함

 

 

4. 위상 정렬 적용 예시

• 위상 정렬을 수행한 결과, 왼쪽에서 오른쪽 방향으로 정점을 나열했을 때, 왼쪽의 정점으로 이동하는 간선이 없어야 함

 

(예시)

• 위상 정렬과 비위상 정렬 예시

- (C) 정점에서 D로 가는 간선이 존재하지만, 방향을 역행하면 위상 정렬이 아님

 

• 라면 끓이기 작업의 선후 관계

- 라면에 물 붓기와 라면 봉지 뜯기는 선후 관계가 없음

- 라면 넣기와 수프 넣기도 선후 관계가 없음

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.