참고 블로그:
[Python] 그래프 - 위상 정렬(Topology Sort) 알고리즘 구현하기
다음과 같은 조건을 가진 그래프라면 위상 정렬을 할 수 있다. 간선이 방향성을 가진 그래프여야 한다. 그래프 내부에 순환(Cycle)이 없어야 한다. 즉, 위상 정렬은 DAG(Direct Acyclic Graph)에 대해서만
velog.io
한마디로 "1을 하기 전에는 2를 할 수가 없다." 라는 일정한 순서가 정해져 있을 때 쓰기 편한 알고리즘이라고 한다.
위상정렬의 step은 다음과 같다.
1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내고 해당 원소와 연결된 간선을 제거한다.
3. 간선을 제거한 뒤에 0이 진입차수가 0이 된 정점을 큐에 삽입한다.
4. 위 과정을 반복한다.
과정만 보았을 때 진입차수를 기록할 count라는 list와 그래프가 있으면 간단하게 구현할 수 있을 것 같다.
