PS/Algorithms
[Java] Topological Sort(위상 정렬) - 방향성 있으며 사이클 없는 그래프
CalicoCat22
2022. 2. 13. 21:45
https://bcp0109.tistory.com/21
위상정렬 Topological Sort (Java)
위상정렬 연습 문제 1 연습 문제 2 위상 정렬은 그래프 정렬을 말합니다. 그래프의 순서를 정렬하기 때문에 조건이 있습니다. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사
bcp0109.tistory.com
필요한 정보
1) 각 노드가 가리키는 노드 번호에 대한 정보
2) 각 노드를 수행하기 전에 탐색되어야 하는 노드의 개수 (inDegree)
3) 탐색 시작 시점에 inDegree == 0인 노드 (출발 노드의 위치, 개수)
사이클 유무 확인 방법
탐색한 노드들을 Answer Queue에 넣어놓았을 때
크기가 n보다 작다면 => 사이클이 존재!