위상 정렬(Topological sorting) [Java]

목차 1. 위상정렬이란? 2. 위상정렬의 과정 3. 위상정렬 구현 1. 위상정렬이란? 위상정렬은 사이클이 존재하지 않는 방향 그래프에서 정점들을 정렬하는 알고리즘이다. 대표적인 실생활의 예로 대학교의 선후수 교과과정이 있다. 위와 같은 상황에서 과목을 듣는 순서를 짜는 것이 위상정렬의 한 예이다. 만약 사이클이 있다면 선후 관계가 모호해지기 때문에 사이클은 올 수 없다. 2. 위상정렬의 과정 위 그래프를 한번 위상정렬해보자. 먼저 들어오는 간선이 없는 A가 제일 앞에 올 것이다. A에서 나가는 간선을 보면 B, C, D를 향해 있다. 이것의 의미는 B, C, D를 거치기 전에 반드시 A가 등장해야한다는 의미이다. 지금 상태에서는 A가 제일 앞에 등장했으니 A에서 나가는 간선은 의미가 없다. 그러므로 A와..

→2021.08.07