[알고리즘] 위상 정렬(Topology Sort)

위상 정렬

• 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
• 방향 그래프, 사이클이 없는 그래프에서만 적용이 가능하다 (DAG : Directed Acyclic Graph)
• 모든 원소를 방문하기 전에 큐가 빈다면 사이클 존재
• 그래프에 사이클이 존재하는지 판별 + 위상 정렬 결과 획득

알고리즘 개요

1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 모든 간선을 제거한다.
3. 간선 제거 이후 진입차수가 0인 정즘을 큐에 삽입한다.
4. 큐가 빌 때까지 2,3번을 반복한다. 모든 원소 방문 전에 큐가 빈다면 사이클 존재.

소스 코드

public void topologySort() {
	int[] inDegree = new int[MAX];
    int[] result = new int[MAX];
    Queue<Integer> q = new LinkedList<>();
    
    //진입 차수가 0인 노드를 큐에 삽입 
    for (int i = 1; i <= N; i++)
    	if (inDegree[i] == 0) q.add(i);
    
    //정렬이 완전히 수행되려면 정확히 N개 노드를 방문
    for (int i = 1; i <= N; i++) {
    	if (q.isEmpty()) {
        	//사이클 발생
        	return;
        }
        int x = q.poll();
        result[i] = x;
        for (int j = 0; j < edge[x].size(); j++) {
        	int y = edge[x].get(j);
            // 새롭게 진입차수 0이 된 정점을 큐에 삽입
            if (--inDegree[y] == 0)
            	q.add(y);
        }
    }
    -> result 배열에 정렬 완성 
}