위상정렬

유향 그래프의 꼭짓점들(vectex)을 변의 방향을 거스르지 않도록 나열하는 것

ex) 순서가 있는 작업들을 수행할 때 순서 결정하기

1. DFS

스택에 들어가는 순서 : 7 -> 5 -> 2 -> 6 -> 3 -> 4 -> 1

위상정렬 순서 : 1 -> 4 -> 3 -> 6 -> 2 -> 5 -> 7

(여러 경우의 수 발생할 수 있다)

2. indegree 이용하기

(indegree : 한 정점에서 자신에게 들어오는 방향인 간선의 수)

1번 정점의 indegree 개수 = 0
2번 정점의 indegree 개수 = 1
3번 정점의 indegree 개수 = 2
4번 정점의 indegree 개수 = 3
5번 정점의 indegree 개수 = 0

indegree 개수가 0인 정점을 큐에 추가
큐의 front를 추출해 해당 정점과 연결되어 있는 정점들의 indegree 1 감소시키고 0이라면 큐에 추가

위 과정을 반복하면 큐에 삽입된 순서가 위상정렬의 순서가 된다

• 관련 문제 : BOJ 1005번 ACM Craft 문제