[알고리즘] 그래프 - 위상 정렬(Topology Sort)

위상 정렬 알고리즘 (Topology Sort) 위상 정렬이란 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스리지 않도록 순서대로 나열하는 것이다. ex> 선수 과목을 고려한 학습 순서 결정 (우선순위) 선수 과목구조란 여러 수강 과목이 존재하는 경우 "c언어 과목을 들어야 알고리즘 강의를 수강할 수 있다" 라는 규칙을 지켜서 수강 신청을 하는 것을 말한다. 즉 어떤 그래프를 위상 정렬하면 그 결과로 정점들을 원소로 가지는 위상적 순서대로 정렬된 배열이 된다. 진입 차수 : 특정 노드로 들어오는 간선의 수 진출 차수 : 특정 노드에서 나가는 간선의 수 큐를 이용한 위상 정렬 알고리즘 파이썬을 통해서 위상정렬을 구현할 경우 큐를 활용한다. 위상 정렬 알고리즘의 규칙은 아래와 같다. 1. 모든 정점을..