위상 정렬- 정점의 진입차수를 이용하여

위상 정렬의 방법에는 두 가지가 있다.

하나는 진입차수를 이용한 방법이고 다른 하나는 DFS를 특화한 방법이다.

여기서는 진입차수를 이용한 방법에 대해서 알아보도록 하겠다.

 

위상정렬은 진입간선이 0인 것들을 기준으로 삼는다. 따라서 진입간선을 알아내야 한다.

이 때 효율적으로 진입간선의 여부를 알 수 있는 방법이 있는데 바로 제일 처음에 진입 간선의 수를 다 세어 놓는 것이다.

 

A0: A로 들어오는 간선의 수가 0개이다.

B2: B로 들어오는 간선의 수가 2개이다.

 

맨 처음에 A를 시작 노드로 했을 때, A가 B를 가리키므로 B로 들어오는 간선의 수를 하나 감소시켜서 B1로 만든다. (고려대상에서 제외한다.)

효율적으로 진입 차수가 0인 것을 찾는 방법

다 순회하면서 찾는다.? ⇒ 너무 비효율적

해결책: 진입차수가 0인 것들만 따로 모아 놓는다.

⇒ 감소하여 0이 되는 순간 큐에 집어넣는다.