위상 정렬(Topological Sorting)

 

❒ Description

---

Course Schedule 문제를 풀면서 위상 정렬을 사용하는 풀이 방법을 알게 됐다.

 

[ 같이 참고하면 좋은 문제들 ]
※ 2024.09.24 추가 : [LeetCode#310] Minimum Height Trees

 

 

 

❒ DAG (Directed Acyclic Graph)

---

위상 정렬에 대해 공부하기 전 DAG에 대해서 알아보자.

 

1. 정의

유향 비순환 그래프 또는 방향 비순환 그래프는 컴퓨터 과학 분야의 용어로 하나로서, 방향 순환이 없는

무한 유향 그래프이다. 이해하기 쉽게 표현하면, 모든 간선들은 방향을 가지고, 어떠한 노드에서 출발해도

다시 그 노드로 돌아오는 순환이 존재하지 않는 그래프다. DAG의 특성은 다음과 같다.

 

Directed (유향성)

• 그래프의 각 간선이 방향을 가진다

 

Acyclic (비순환성)

• 그래프에 순환(Cycle)이 존재하지 않는다. 만약 그래프에 순환이 있다면, 그것은 DAG가 아니다.

 

즉, DAG는 유향성과 비순환성을 가지는 특수한 종류의 그래프다.

 

 

2. 사용 예

‣ 작업 스케쥴링 

DAG는 작업의 순서를 나타내는 데 유용합니다. 작업 A가 끝나야만 작업 B를 시작할 수 있는 경우,

DAG로 이 관계를 표현할 수 있다.

 

‣ 컴파일러의 토폴로지 정렬

DAG는 컴파일러에서 모듈 간의 의존성을 관리할 때 사용된다. 모듈이 다른 모듈에 의존하는 경우,

이 관계를 DAG로 표현하고, 이 의존성 순서에 따라 모듈을 컴파일할 수 있다.

 

‣ 버전 컨트롤 시스템

Git과 같은 버전 관리 시스템에서, 각 커밋은 DAG의 노드로 표현된다. 이전 커밋에 대한 참조는 

유향 간선으로 표현되며, 순환이 없는 구조로 되어있다.

 

 

 

 

 

❒ 위상 정렬이란?

---

위상 정렬은 방향 그래프에서 사이클이 없는 경우에, 노드들의 순서를 정하는 알고리즘이다. 특히 Kahn의

위상 정렬 알고리즘은 진입 차수(들어오는 간선의 개수)가 0인 노드를 먼저 제거하면서 진행된다. 이 과정에서

진입 차수가 0인 노드를 계속해서 큐에 추가하고, 이를 제거하면서 새로운 진입 차수가 0인 노드를 찾는 방식이다.

 

 

 

 

 

❒ 동작 과정

---

위상 정렬을 구현하기 위해서는 Queue를 사용해야 한다.

1. 우선 진입 차수가 0인 모든 노드를 Q에 넣는다.

2. Q에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거한다. 

3. 새롭게 진입 차수가 0이 된 노드를 Q에 넣는다.

4. Q가 빌 때까지 2~3을 반복한다. 

 

여기에 이미지가 첨부되어 있어서 이해하기가 쉬웠다.

 

 

 

 

❒ 시간 복잡도

---

노드와 간선을 모두 확인하는 것을 고려하여 O(V) + O(E) = O(V+E)의 시간복잡도를 가진다.

1. O(V) : 차례대로 모든 노드를 확인한다.
2. O(E) : 해당 노드에서 출발하는 간선을 차례대로 제거한다. 

 

 

 

 

---