위상 정렬 (Topological Sort)

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

 

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

위상 정렬의 핵심 아이디어

위상 정렬은 노드들 간의 의존 관계를 고려하여 모든 노드를 순서대로 나열하는 과정입니다. 

예를 들어, 코스 수강 문제에서 A → B가 있으면, A를 먼저 수강해야 하고 그 후에 B를 수강할 수 있습니다. 

따라서 위상 정렬은 이와 같은 의존 관계를 가진 작업들을 순서대로 나열하는 방식입니다.

위상 정렬의 활용

작업 스케줄링: 여러 작업 간의 의존성을 만족시키면서 작업을 순서대로 실행하는 데 사용됩니다.

코스 스케줄링 문제: 특정 과목을 듣기 위해 다른 과목을 먼저 들어야 하는 상황에서 과목을 들을 수 있는 순서를 정합니다.

컴파일러: 모듈 간 의존 관계가 있을 때, 모듈을 어떤 순서로 컴파일해야 하는지 결정할 때 사용됩니다.

//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);