위상정렬

위상정렬을 왜 쓰는가? 

쉬운 예로 설명할 수 있겠다. 

1) 스타크래프트를 할 때 고급 건물을 짓기 위해서 먼저 지어야 되는 건물들이 있다.

이러한 순서를 나타낸 것을 위상정렬이라고 할 수 있겠다. 

이러한 순서와 관계를 정리해주는 것을 위상정렬이라고 하겠다. 

2) 학교 수강 과목 중에 반드시 선수되어야 할 과목들이 있을 것이다. 이렇게 어떠한 과목을 듣기 전에 듣고 가는 과정을 나타내는 것을

위상정렬이라고 할 수 있겠다. 

위상정렬를 구하는 방법에 대해서 간단히 설명하겠습니다.

우선 위상정렬은 방향이 있는 비순환 그래프에서 가능한 것입니다. 

위와 같은 그래프가 있습니다. 

1) 우선 위상정렬을 구하기 위해서는 진입하는 간선이 없는 노드를 찾습니다.

2) 찾은 노드를 저장합니다.

3) 이 노드에서 빠져나가는 간선들을 다 지워줍니다.

4) 1)의 과정으로 돌아갑니다. 

자신으로 들어오는 간선이 없는 노드를 indegree가 0인 노드라고 표현합니다.

이러한 과정을 반복해서 나온 노드들의 번호들의 순서가 위상정렬이 됩니다. 

다음과 같은 반복이 I까지 가게됩니다.