위상 정렬 (topology sort)
- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
- 기능 : 노드 간의 순서를 결정
- 특징 : 사이클이 없어야 함 -> 사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없어 위상 정렬 적용 불가
- 시간 복잡도 : (노드 수 V, 에지 수E) O(V+E)
- 항상 유일한 값으로 정렬되지 않음
- 원리
1. 진입 차수 : 자기 자신을 가리키는 에지의 수
그래프는 사이클이 없는 상태로 ArrayList로 그래프를 구성하였음
진입 차수 배열 D를 세팅함 -> 각자의 진입 차수로 업데이트
2. 진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장
인접 리스트에서 선택된 노드가 가리키는 노드들의 진입 차수를 1씩 빼줌
예) 진입 차수가 0인 노드 1을 선택하여 위상 정렬 배열에 저장한 후,
인접 리스트 1의 연결값 2, 3의 진입 차수를 1씩 빼준다
-> 진입 차수 배열에서 2와 3이 0이 되고 계속해서 진입 차수가 0인 2 또는 3을 선택해준다.
👉2를 먼저 선택할 수도, 3을 먼저 선택할 수도 있기 때문에 위상 정렬이 늘 같은 정렬 결과를 보장하지 않는다는 것!
-> 이 과정을 모든 노드가 정렬될 때까지 반복!
