위상정렬(topological sorting)

1. 개념

위상 정렬은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequistie) 구조를 예로 들 수 있다.

만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로,

특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다.

이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기

위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가

나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다.

이 점에서 비순환 유향 그래프이다.

*출처 : 위키디피아

2. 구현

1) DFS

DFS를 실행하면서 DFS가 끝났을때 역순으로 순서를 기록해준다.

2) indegree (자신에게 들어오는 간선의 수)

모든 정점의 indegree의 개수를 세어준 후에 queue에 indegree가 0인 정점을 삽입하고,

해당 정점에서 뻗어나간 다른 정점의 indegree 수를 하나씩 줄여준다.

정점의 수만큼 반복하면된다.

[위상정렬 예제 1 : http://gyutts.tistory.com/72]

[위상정렬 예제 2 : http://gyutts.tistory.com/76]