[알고리즘/python] 위상정렬

지난 시간 DFS, BFS를 이용해 그래프 탐색하는 방법을 배웠다. 다음 과제인 '위상정렬' 문제를 풀기 전에 그 개념에 대해 공부해보려한다. 

---

위상정렬 (Topological-Sort)

 

순서가 정해져있는 일련의 작업을 차례대로 수행해야할 때 사용하는 알고리즘

 

- 조건; dag (Directed Acyclic Graphs, 비순환 방향 그래프) 

- 모든 방향의 간선이 왼쪽 > 오른쪽 향하며 수평선을 따르는 정점들의 순서

- 시간 복잡도 = O(V+E); 모든 노드를 확인(O(V))하면서, 해당 노드에서 출발하는 간선을 차례대로 제거해나감 (O(E))

- 해가 여러개일 수 있음

 

구현 방법

 

의사코드

1. 진입 차수 테이블을 만든다.

2. 진입 차수가 0인 정점을 큐에 삽입한다. (이 말은 출발점이 여러개가 될 수 있다는 말!)

3. 큐가 빌 때까지 다음의 과정을 반복한다.

- 큐에서 원소를 꺼내 해당 노드에서 나가는 (인접) 간선을 그래프에서 제거

- 새롭게 진입차수가 0이 된 노드를 큐에 삽입

 

테스트 케이스

 

실습 코드

Study-Algorithm/algorithm_practice/graph/topological_sort.py at main · ddubbu-dev/Study-Algorithm

 

 

 

참고자료