위상 정렬 계산기

진입차수가 0인 정점을 꺼내고 그 정점이 가리키던 화살표를 지우기를 되풀이합니다(칸 알고리즘). 진입차수란 그 정점으로 들어오는 화살표 수, 곧 아직 안 끝난 선행 조건의 개수입니다. 0인 것은 지금 바로 할 수 있는 일이므로 순서에 넣고, 지운 뒤 다시 0이 된 것을 이어서 꺼냅니다.

대부분 여러 개입니다. 진입차수가 0인 정점이 한 번에 여럿이면 아무 것이나 먼저 골라도 되기 때문입니다. 이 계산기는 그럴 때 이름이 앞서는 것을 먼저 꺼내 그중 하나를 보여 주고, 가능한 순서가 모두 몇 가지인지를 따로 세어 알려 줍니다(정점 16개까지).

위상 정렬 자체가 존재하지 않습니다. A → B → C → A라면 어느 것도 먼저 할 수 없기 때문입니다. 칸 알고리즘에서는 진입차수 0인 정점이 더는 없는데 남은 정점이 있는 것으로 드러나며, 그 남은 정점들이 곧 순환에 얽힌 것들입니다. 빌드 도구가 circular dependency라며 멈출 때 알려 주는 목록이 이것입니다.

일을 아무리 많은 사람에게 나눠 맡겨도 줄일 수 없는 최소 단계 수입니다. 그 사슬 위의 일들은 서로 기다려야 하기 때문입니다. 반대로 같은 단계에 있는 일들은 서로 기다릴 필요가 없어 한꺼번에 할 수 있어, 일정을 줄이려면 임계경로 위의 일부터 손대야 합니다.

선수과목 순서, 빌드·패키지 설치 순서, 스프레드시트 수식 갱신 순서, 작업 일정이 모두 같은 문제입니다. «A를 끝내야 B를 할 수 있다»는 관계만으로 한 줄 순서를 찾는 일이며, 관계가 돌아오지만 않으면 언제나 답이 있습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.