[그래프] 위상 정렬

✔ 위상 정렬

위상 정렬이란?

• 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
• 항상 유일한 값으로 정렬되지 않음
• V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E)

위상 정렬 과정

1. ArrayList(인접 리스트)로 그래프를 표현
2. 자기 자신을 가리키는 엣지의 개수를 뜻하는 진입 차수에 대한 진입 차수 배열을 업데이트
3. 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장
4. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 뺀 후, 진입 차수 배열 업데이트
5. 이 과정을 모든 노드가 정렬될 때까지 반복

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn