알고리즘 - 위상정렬 (Topological Sort)

알고리즘 - 위상정렬 (Topological Sort)

DAG(비순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 알고리즘으로 위상정렬은 각 정점을 우선순위에 따라 배치한다. 일반적으로 결과는 유일하지 않다.

 

jina-developer.tistory.com/112

자료구조 - DAG (Directed Acyclic Graph)

 

1. 각 노드들의 진입 차수 계산
2. 진입 차수가 0인 노드들을 큐에 삽입
3. 큐에서 노드를 꺼내 연결된 간선을 제거
4. 제거로 인해 진입 차수가 0이 된 노드를 큐에 삽입
5. (3)~(4) 번을 반복하며 큐가 비었으면 종료

gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html