위상 정렬을 구하는 두 가지 방법

위상 정렬이란 다음과 같은 그래프가 있다 각 노드는 해야할 작업이며 작업은 이전 작업이 끝나야 시작할 수 있다 예를 들어 3번 작업을 하기 위해서는 2번 작업을 먼저 해야하고 2번 작업을 하기 위해서는 1번 작업을 먼저해야한다 그러므로 작업순서는 1 2 3이 된다 그러면 다음과 같은 경우를 보자 3번이나 5번 작업을 하기 위해서는 2번 작업을 먼저 해야하고 2번 작업을 하기 위해서는 1번과 4번 작업을 해야한다 그러므로 작업 순서는 1 4 2 3 5 or 4 1 2 3 5 or 1 4 2 5 3 or 4 1 2 5 3 이 될 수 있다 이처럼 작업 순서가 있는 경우 작업 순서를 구하는 것을 위상 정렬이라 한다 위상 정렬하는 방법 위상 정렬을 구하는 방법에는 두 가지가 있다 진입 차수가 0인 노드를 지우면서..