1. 위상 정렬 알고리즘(Topological Sort Algorithm)이란?
위상 정렬 알고리즘(Topological Sort Algorithm)은 어떤 일을 하는 순서를 찾는 알고리즘입니다. 만약 먼저 방문해야 하는 노드가 있다면 그 노드를 방문해야 현재 노드에 방문할 수 있습니다. 위상 정렬 알고리즘은 선행 노드가 무조건 수행되어야 하기 때문에 사이클이 발생하지 않습니다.
2. 위상 정렬 알고리즘(Topological Sort Algorithm) 동작 원리?
위상 정렬이란 선행 노드가 수행이 되었을 때, 즉 진입 차수가 0일 때 현재 노드를 방문할 수 있습니다.
위 그래프의 진입 차수는 다음과 같습니다.
이때 진입 차수가 0인 노드들을 queue에 넣어줍니다.
queue에서 숫자를 하나씩 빼주면서 연결되어 있는 노드의 진입 차수를 하나씩 빼주면서 진입 차수가 0이 되면 queue에 넣어줍니다.
위와 같은 방법으로 반복해줍니다.
위상 정렬을 이용하여 다음 문제들을 풀 수 있습니다.
https://rudalsd.tistory.com/73?category=1064612
[ 백준 ] 1948번 - 임계경로 (C++)
https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음..
rudalsd.tistory.com
'알고리즘' 카테고리의 다른 글
[ 알고리즘 ] 단절점(Articulation Point) (0) | 2022.08.26 |
---|---|
[ 알고리즘 ] 강한 연결 요소 추출 알고리즘(Strongly Connected Component) (0) | 2022.07.23 |
[ 알고리즘 ] KMP 알고리즘(KMP Algorithm) (0) | 2022.07.19 |
[ 알고리즘 ] 컨벡스 헐 알고리즘(Convex Hull Algorithm) (0) | 2022.07.16 |
[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem) (0) | 2022.07.10 |