위상 정렬 (Topological Sort)

처리해야할 여러가지 일들이 있고, 이들 사이의 선후 관계가 있는 그래프.
DAG (Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)  조건.

 

• 진입 차수(indegree)를 이용한 정렬
• 탐색큐, 결과큐 사용 O(|V|+|E|)
• 진입 차수가 0이 아닌 정점이 남아 있으면 사이클이 있는 그래프

//V : 정점집합, E : 간선집합, Q : 탐색큐
//Adj[v] : 정점 v의 인접 정점 리스트
//indegree[v] : v의 진입차수
//resultQ : 정렬된 정점

//각 정점의 진입차수 계산 선행

for (v : V)
	if (indgree[v] == 0)	//간선이 없는(indegree가 0인) 정점을 큐에 모두 넣기
    	Q.offer(v); resultQ.offer(v);
        
while (!Q.isEmpty())
	v = Q.poll();
    for (인접정점 u : Adj[v])
    	indegree[u]--;		//이전 정점은 지나갔으니 진입 차수 차감
        if (indegree[u] == 0)	//진입차수가 0이면 큐에 넣기
        	Q.offer(u); resultQ.offer(u);