[알고리즘] 위상정렬(Topological Sort)

 Concept 

1) 개념

"순서가 정해져 있는 작업들의 순서를 정해주기 위해 사용하는 알고리즘."

 

방향 그래프(유향 그래프, Directed Graph)의 꼭짓점(Vertex)들을 방향에 거스르지 않도록 나열하는 것을 의미한다.

위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. (시작점을 찾을 수 없기 때문)

 

 

ex) 선수과목(prerequisite) 구조, 업무 일정 배치(PERT - 일정관리 평가 분석)

 

2) 수행 과정

 

① 자기 자신을 가리키는 변이 없는 버텍스(노드)를 찾는다.

② 찾은 버텍스를 출력하고, 출력한 버텍스와 그 버텍스에서 출발하는 간선(edge)을 삭제

③ 아직 그래프에 버텍스가 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료한다.

 

3) 시간복잡도

O( | V | + | E | ) : 정점과 간선의 갯수 만큼의 시간 복잡도가 발생

 

 출처 

- 위키(ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC)