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보다 작다면 => 사이클이 존재!