programming_study_blog

국어사전에서는 위상을 "어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태" 라고 풀이한다.

이 뜻풀이에서 '사물' 대신 '정점'으로 바꾸면 다음과 같다.

"어던 정점이 다른 정점과의 관계 속에서 가지는 위치"

이 말은 그래프 안에서 서로 인접해 있는 정점 사이의 관계에 '위치'라는 속성이 존재한다는 뜻이다.

이 위치는 앞/뒤일 수도 있고 위/아래일 수도 있다.

뭐든 괜찮지만 우리는 앞/뒤관계라고 생각한다.

이 위치 속성은 간선의 방향에 의해 결정된다.

간선이 뻗어나오는 정점이 앞이 되고 간선이 들어가는 정점이 뒤가 된다.

이 앞/뒤 관계를 차근차근 정렬하는 것이 위상정렬이다.

아무 그래프에 대해서나 위상정렬을 할 수 있는 것은 아니다.

방향성이 없으면 정점의 앞뒤 관계를 어찌 판단하겠으며 사이클이 있다면 시작과 끝을 어떻게 정의내릴 수 있을까?

그래서 위상정렬이 가능하려면 첫째로 그래프에 방향성이 있어야 하고 둘째로 그래프 내에 사이클이 없어야 한다. 이러한 그래프를 DAG(Directed Acyclic Graph)라고 한다.

위상정렬의 동작 방식

그래프는 정점의 집합과 간선의 집합으로 이루어져 있다.

간선이 방향성을 가지는 경우에는 어느 정점이 선이고 어느 정점이 후인지도 설명한다.

정점은 두 가지 종류의 방향성 간선을 가질 수 있는데 그중 하나는 정점으로 들어가는 진입 간선(Incoming Edge)이고, 다른 하나는 진출 간선(Outgoing Edge)이다.

진입 간선과 진출 간선 이야기를 꺼낸 것은 이들에 대한 개념이 위상 정렬 알고리즘을 이해하는 데 필요하기 때문이다. 위상 정렬은 다음과 같은 과정을 거쳐 완성된다. 

1. 리스트를 하나 준비한다.

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

3. 모든 정점에 대해 2를 반복하고, 그래프 내에 정점이 남아 있지 않으면 정렬을 종료한다. 이 때 리스트에는 위상 정렬된 그래프가 저장된다.

DFS를 이용한 위상정렬

위상정렬은 이해하기 쉽고 자신의 임무를 제대로 해낸다.

이 알고리즘과 똑같이 위상정렬을 수행하지만 조금 더 우아하게 문제를 푸는 방법도 있다.

바로 DFS를 이용하여 위상정렬을 하는 것이다.

DFS를 이용한 위상 정렬 알고리즘은 다음과 같다.

1. 리스트를 하나 준비한다.

2. 그래프에서 진입 간선이 없는 정점에 대해 DFS를 시행하고 탐색 중에 더 이상 옮겨갈 수 있는 인접 정점이 없는 정점을 만나면 이 정점을 리스트의 새로운 '헤드'로 입력한다.

3. 2를 반복하다가 더 이상 방문할 정점이 없으면 DFS를 종료한다. DFS가 끝난 후 리스트에는 위상 정렬된 그래프가 남는다.