크래프톤 정글 6기 TIL - Day 12| 위상 정렬

뭔가 마땅히 찾지 못한 짤

 

위상 정렬
Topological Sort

 

정의 

방향 그래프에서 간선으로 주어진 정점 간 선후 관계를 위배하지 않도록 나열하는 정렬

✨ 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다.

           DAG(Directed Acyclic Graph)

 

구현

 

1. 제일 앞에 오려면 자신보다 앞에 있는 정점이 하나도 없어야 한다.

= 자신에게 들어오는 정점이 없어야 한다.( indegree = 0 )

 

 

2. A를 위상정렬에 추가한 이후로는 A에서 다른 정점으로 나가는 간선이 의미가 없다.

→ A와 A에서 뻗어 나가는 간선을 모두 지운다.

 

 

3. 그래프에서 제일 앞에 위치 할 수 있는 정점. → 자신에게 들어오는 간선이 없는 정점 = C, G

 

4. 정점 C에서 뻗어나가는 간선 삭제. 제일 앞에 위치할 수 있는 정점 = D, G

 

5. 정점 D에서 뻗어나가는 간선 삭제 → 그래프가 분리된다. ( 신경안써도됨! )

 

6. 자신에게 들어오는 간선이 없는 정점 = B,G

 

7. 자신에게 들어오는 간선이 없는 정점 = B,F

 

8. 마지막으로 남은 원소 F = 마지막

 

✨ 매 순간마다 들어오는 간선이 없는 정점을 제거하는 방식으로 위상정렬을 구현할 수 있다.

 

구현과 편의를 위한 성질

1. 정점과 간선을 실제로 지울 필요 없이 미리 indegree의 값을 저장했다가 매번 뻗어나가는 정점들의 indegree 값만 1 감소시켜도 과정을 수행 가능

2. degree가 0인 정점을 구하기 위해 매번 모든 정점들을 다 확인하는 대신 목록을 따로 저장하고 있다가 직전에 제거한 정점에서 연결된 정점들만 추가

 

위상 정렬 알고리즘

1. 맨처음 모든 간선을 읽으며 indegree 테이블을 채움

2. indegree가 0인 모든 정점들을 모두 큐에 넣음

3. 큐에서 정점을 꺼내어 위산 정렬 결과에 추가

4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴. 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가

5. 큐가 빌 때까지 3,4번 과정을 반복