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

공부한 날짜: 2021. 11. 03

 

-위상: 어떤 정점이 다른 정점과의 관계속에서 가지는 위치

-위상 정렬의 조건

(1) 그래프에 방향성이 있어야 한다

(2) 그래프 내의 사이클이 없어야 한다 

 

-정점이 가질 수 있는 방향성 간선

(1) 진입간선

(2) 진출간선 

 

-위상정렬 과정

ㄱ. 리스트 하나 준비

ㄴ. 그래프에서 진입간선이 없는 정점을 리스트에 추가, 해당 정점 자신과 진출간선을 제거

ㄷ. 모든 정점에 대해 ㄴ.을 반복하고 그래프에 정점이 남아 있지 않으면 정렬 종료. 리스트에는 위상 정렬된 그래프가 저장됨

 

-깊이 우선 탐색으로 위상 정렬하기

ㄱ. 리스트 하나 준비

ㄴ. 그래프에 진입 간선이 없는 정점에 대해 깊이 우선 탐색 시행, 탐색 중에 인접 정점이 없는 정점을 만나면 해당 정점을 리스트의 새로운 '헤드'로 입력

ㄷ. ㄴ. 반복하다 더이상 방문할 정점이 없으면 깊이 우선 탐색을 종료함. 깊이 우선 탐색이 끝난 후 리스트에는 위상 정렬된 그래프가 남음