Topological Sort는 기본적으로 DFS를 통해 구현합니다. DFS에 대한 내용은 아래 글에 있습니다.
[알고리즘] 깊이 우선 탐색(DFS) - Python
깊이 우선 탐색 Depth-First Search 깊이 우선 탐색(DFS)이란 그래프를 탐색하는 방법의 일종으로, root node에서 시작해서 깊이 방향(Depth)으로 확장하는 방식의 탐색을 말합니다. 깊이 방향이란, 한 노드
stevenkim1217.tistory.com
Topological Sort
Topological Sort란 그래프를 표현하는 한 가지 방식입니다. 그래프를 수평적으로, 즉 모든 노드를 한 줄로 나열하여 정렬하는 방식입니다. Topological Sort는 Directed Acyclic Graph(DAG)에서 수행됩니다.
- Directed Acyclic Graph(DAG): 그래프 연결에 방향이 있고(Directed), 한 곳에서 순환이 발생하지 않는(Acyclic) 그래프(Graph)를 의미합니다.
다음과 같이 옷을 입은 순서를 나타낸 그래프가 있다고 하겠습니다. 이때 이 아래의 그래프를 DFS로 탐색했고, 각 노드 옆의 숫자는 (discovered time / finish time)을 의미합니다.
위 그래프를 수평적으로 눌러 나탄내면 아래와 같습니다. DFS의 방문 종료 시점(finish time)을 기준으로 내림차순 정렬합니다. 현재 slash의 오른쪽에 18,16,15,14,10,8,7,5,4 순으로 노드가 정렬된 것을 볼 수 있습니다.
이 Topological 개념이 다른 그래프 알고리즘에서 주요하게 사용됩니다.
Running Time
DFS를 통해 탐색하기 때문에, DFS의 수행 시간과 동일합니다: O(V+E)
이 글은 다음의 자료를 참고하여 만들어졌습니다.
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare
This course is an introduction to mathematical modeling of computational problems, as well as common algorithms, algorithmic paradigms, and data structures used to solve these problems. It emphasizes the relationship between algorithms and programming and
ocw.mit.edu
'컴퓨터 과학(Computer Science) > 알고리즘(Algorithm)' 카테고리의 다른 글
| [알고리즘] 벨만-포드 알고리즘(Bellman-Ford Algorithm) (0) | 2023.12.01 |
|---|---|
| [알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) (0) | 2023.12.01 |
| [알고리즘] DAG 최단 경로 문제(DAG Shortest Path Problem) (0) | 2023.12.01 |
| [알고리즘] 깊이 우선 탐색(DFS) - Python (0) | 2023.11.10 |
| [알고리즘] 너비 우선 탐색(BFS) - Python (0) | 2023.11.10 |
