topolopgy sort1 [JAVA] 위상정렬 (TopologySort) - 위상정렬이란? 순서가 정해져 있는 작업들의 목록들을 가지고 전체 작업 순서를 결정하도록 하는 알고리즘. 이를 위해서는 사이클이 없는 방향그래프에서만 해야한다. 아래 그래프로 예를 들겠다. 1번 작업은 2번보다 먼저 해야한다. 이것을 방향그래프로 나타내었다. 2번은 5번 보다 먼저 해야 한다. 5번은 4번 보다 먼저 해야한다. 만약 위와 같은 작업 스케줄이 있다면 어떻게 진행하면 좋을 것인가? 1 - 2 - 3 - 5 - 4 1 - 3 - 2 - 5 - 4 위 2가지 경우중에서 한가지 선택하여 진행하면 된다. 먼저 차수에 대해 정의하겠다. 한 정점의 차수 = 해당 정점보다 먼저 선행되어야 하는 작업의 수 예를들어, 3번의 차수는 1이다. 1번 작업이 선행되어야 하기 때문이다. 5번의 차수는 2이다. 2.. 2021. 2. 24. 이전 1 다음
