그래프 Topological Sort 알고리즘

 

이전시간에 BFS와 DFS까지 다뤘습니다. 이번에는 DFS로 만들 수 있는 Topological Sort (위상정렬) 알고리즘을 알아봅시다.

Topological Sort 위상 정렬이란

Toplological Sort (위상 정렬) 알고리즘이란 DAG의 정점들을 선형으로 정렬하는 방법입니다.

이 때 위상정렬의 핵심 규칙은 정렬된 결과에서 u는 반드시 v 앞에 와야한다는 것입니다.

정점 (u, v)는 u에서 v로 가는 방향성 간선인데 이 때 이 규칙을 만족해야합니다.

예를 들어 A -> B -> C 이런 그래프가 있다면

A는 B보다 앞에 와야 합니다.
B는 C보다 앞에 와야 합니다.
따라서 유일한 정렬 순서는 A,B,C입니다

이 순서는 전체순서입니다. 전체순서란 아래에서 확인 가능합니다.

 

부분 순서 (Partial Order)

정의: 일부 원소들만 비교 가능한 순서입니다.
특징: 모든 원소 쌍이 비교 가능한 것은 아닙니다.
예시: a > b이고 b > c이지만 a와 c는 비교 불가할 수 있습니다. 아예 둘이 연관이 없을수도 있단겁니다.

 

전체 순서 (Total Order)

정의: 모든 원소 쌍이 비교 가능한 순서입니다.
특징: 모든 원소가 서로 비교되어 순서가 정해집니다.
예시: a > b, b > c, a > c 모두 성립합니다.

위상 정렬은 부분순서를 전체순서로 변환하는 과정입니다.

 

DAG란

DAG(Directed Acyclic Graph)란 방향성 비순환 그래프를 뜻합니다.

즉 화살표가 있는 + 순환이 없는(돌아갈 화살표가 없는) 그래프입니다.

 

유니티를 쓰셨다면 패키지 매니저로 한 패키지 설치시 다른 패키지도 같이 종속성으로 연달아서 설치하게 되는것처럼 많은 곳에 쓰이는 그래프 방식입니다.

 

어쨋든 Topological Sort 위상정렬 알고리즘을 응용해서 다양한 곳에 쓰일 수 있습니다.

 

- Build Systems (빌드 시스템)
소프트웨어 컴파일 순서 결정

- Task Scheduling (작업 스케줄링)
프로젝트 일정 관리
- Course Scheduling (수업 일정 관리)
대학 커리큘럼 설계
- Package manager (패키지 관리자)
소프트웨어 패키지 설치 순서

 

 

알고리즘 간단하게 미리보기 예시

TOPOLOGICAL-SORT(V, E):
1. DFS로 모든 정점의 종료 시간(finishing time) 계산
2. 종료 시간이 큰 순서대로(감소하는 순서로) 정점들을 출력

 

 

아래는 그래프로 그렸을 때 생김새입니다.

야구 포수가 옷 입는 순서를 DAG로 나타낸 그림이라네요.

보다시피 그냥 DAG의 특징이 잘 나타납니다.

 

 

Acyclic, Lemma

위상 정렬은 DAG 그래프여야합니다.

Acyclic이란 Cycle를 만들지 말라는 순환이 없는 그래프여야한다는 겁니다.

 

Lemma란 수학이나 이론 컴퓨터 과학에서 사용되는 용어로, 더 큰 정리를 증명하기 위해 사용되는 보조적인 명제나 진술을 의미합니다.

즉, DAG의 래마란 방향 그래프 G가 비순환 그래프(DAG)인지 확인하는 방법으로, DFS(깊이 우선 탐색)를 사용하여 백 엣지(back edge)가 없는지 확인하는 것입니다.

 

이를 증명해봅시다.

 

우선 Cycle이 있다면 순환이 있다는 뜻이므로 백엣지도 있다는 뜻일겁니다.

1. 그래프 G에 사이클 C가 있다고 가정해봅시다.

2. 첫 번째 정점: 사이클 C에서 가장 먼저 발견된 정점을 v라고 하고, 사이클 c에서 v의 이전 엣지들을 (u, v)라고 합니다.
3. 흰색 경로 이론 : 이전글에서 다뤘지만 DFS 탐색 중 d[v] 시점에서 c의 정점들은 v에서 u까지의 흰색 경로를 형성합니다.

(흰색 경로는 아직 방문하지 않은 정점들로 이루어진 경로입니다.)
4. 백 엣지 정의 : 백 엣지란 DFS 탐색 중 현재 정점에서 이전에 방문한 정점으로의 엣지를 의미합니다.
이 경우 u는 v의 자손이므로, (u, v)는 백 엣지입니다.

 

이 1, 2번 구조는 흰색 경로 이론에 의해 u는 v의 후손 노드입니다.

이는 백 엣지의 정의이므로 (u, v)는 백 엣지입니다. 증명끝

 

교수님이 그리신 예시

 

위상정렬은 필수로 해야하는가? -> NO

왜냐하면 ->

DFS가 각 정점을 방문할 때마다 그 정점을 출력합니다.

DFS가 끝난 후 출력된 정점들을 역순으로 나열하면 위상 정렬이 되기 때문입니다.

예시
- DFS 탐색 순서: A, B, C (이 순서로 정점을 방문하고 출력)
- 출력된 리스트: [A, B, C]
- 역순으로 나열: [C, B, A] (위상 정렬 결과)

따라서 종료 시간을 기준으로 정렬할 필요는 없습니다.

어차피 DFS 처리 다한 뒤에 역순으로 나열하면 정렬되니깐요.

종료 시간 기준으로 정렬하는건 아래 감소 시간 순에서 말해보겠습니다.

감소 시간 순 Decreasing Time 

위에서 알고리즘 간단하게 보기 부분 다시 보시면 의사코드인데요.

TOPOLOGICAL-SORT(V, E):
1. DFS로 모든 정점의 종료 시간(finishing time) 계산
2. 종료 시간이 큰 순서대로(감소하는 순서로) 정점들을 출력

코드를 보시면 Decreasing Time 즉 감소 시간순이라는 말이 나옵니다.

이는 종료 시간이 더 늦은 정점은 더 나중에 탐색을 마친 것이므로,

이 정점이 선행 작업을 수행한 후에 후속 작업이 수행된다는 것을 나타냅니다.

따라서, 종료 시간이 감소하는 순서로 정점을 나열하면 위상 정렬의 조건을 만족하게 됩니다.

 

위상정렬 Topological Sort 시간 복잡도

 
Θ( |𝑉| + |𝐸| )

 

왜 세타일까요? 그 이유는 어차피 DFS 처리는 그래프가 단순해서 최선의 경우라해도 여전히 모든 정점 V와 엣지 E를 다 방문해야하기 때문입니다. 최악의 경우에도 똑같습니다.