📌 위상정렬
- 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘
→ 사이클이 존재하면 안됨 - 항상 유일한 값으로 정렬되지 않는다.
| 기능 | 특징 | 시간 복잡도(노드수 : V , 에지 수 : E) |
|---|---|---|
| 노드 간의 순서를 결정 | 사이클이 없어야 함 | O(V+E) |
◾ 위상 정렬의 원리
출처 : https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html
- 진입차수 : 자기 자신을 가리키는 에지의 개수
1. 진입차수 배열 생성
2. 진입차수 내열에서 차수가 0인 노드 선택 후 선택 된 노드를 정렬 배열에 저장한다. 그 후 인접 리스트에서 선택된 노드가 가리키는 노드들의 진입차수를 1씩 뺌
- 사용한 노드는 빼고 다시 진입차수가 0번째 노드를 넣고...반복
- 진입차수 배열을 기준으로 그래프 알고리즘이 돌아간다.
