[Algorithm] 그래프 위상 정렬(Topology Sort)

위상 정렬(topology sort)

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘

 

• 기능: 노드 간의 순서를 결정
• 특징: 사이클이 없어야 함
• 시간 복잡도: O(V+E) (노드 수:V, 엣지 수:E)

위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.

사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.

 

위상 정렬의 원리

1. 진입 차수 (in-degree): 자기 자신을 가리키는 에지의 개수

 

 

2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에서 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀다.

 

 

 

• 참고자료

https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%EC%9E%87-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC&unitId=148396