위상정렬

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

위상 정렬(topological sorting)은 방향 그래프(Directed graph)로 표현된 각 정점(vertex)의 위상 선형 정렬을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있는데, 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 들어야 하는 예 와 마찬가지로 특정 위계가 정의된 구조상에서 위계에 따른 방향으로 정렬 하는 방법이다. 정렬의 순서는 방향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 물건의 제조공정 산출시 유용하게 쓰일 수 있는 방법이다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 사이클이 존재하지 않아야 한다. 이 점에서 비유향 방향 그래프(directed acyclic graph) 이다.

일반적인 위상 정렬의 적용은 주로 업무의 일정을 일어나야 할 순서에 따라 배치하기 위하는 것으로, 이 알고리즘은 프로젝트 관리 기법을 평가 및 분석하기 위한 기법(PERT)에 적용하기 위한 목적을 위해 1960년대 초반부터 연구되었다 (Jarnagin 1960). 이 때, 해당 업무는 정점(vertex)으로 표현되었고, 각 정점을 연결하는 변(edge)는 해당 업무 간의 선후 관계를 표현하였다. 가령, 옷을 다리기 위한 업무는 반드시 옷을 세탁기에 돌리는 업무 뒤에 배치되어야 한다. 이와 같이, 위상정렬은 각 업무를 수행하기 위한 순서를 제공하였다.

위상정렬의 수행과정[편집]

  1. 자기 자신을 가리키는 edge가 없는 vertex를 찾음.
  2. 찾은 vertex를 출력하고 출력한 vertex와 그 vertex에서 출발하는 edge를 삭제
  3. 아직 그래프에 vertex가 남아있으면 단계1로 돌아가고 아니면 알고리즘을 종료시킨다.