Topological Sort (위상정렬)

순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

 

예를 들어보면,

 

위와 같은 커리큘럼에서 알고리즘을 수강하고자 하면 선수과목들을 수강한 후에 들어야한다고 했을 때, 

이산수학 → C프로그래밍 → 객체지향프로그래밍 → 자료구조 → 알고리즘 순서로 수강신청을 하면 된다. 

이 외에도 여러 개의 순서가 존재할 수 있다.

 

선후 관계가 명확했을 때 순서를 결정하여 정렬하는 알고리즘인 것이다.

 

 

🔹 위상 정렬 특징

• 사이클이 발생하지 않는 방향성 그래프에서의 정렬 👉 사이클이 있다면 위상 정렬 수행 X (시작점을 찾을 수 없으므로)
• 큐 또는 스택 사용
• 진입차수 고려 

 

 

 

🕹️ 알고리즘 과정 

 

 

진입 차수는 정점에 들어오는 간선 수이고, 빨간색 숫자는 진입차수를 나타낸 것이다.

 

1. 진입차수가 0인 정점을 큐에 넣는다.
2. 큐에서 정점을 꺼내고 그 정점의 진출 간선을 제거한다.
3. 제거 후 새로 진입 차수가 0이 되는 정점이 있으면 그것을 큐에 넣는다.
4. 큐가 공백이 될 때까지 2, 3번 반복

---

1. 진입차수가 0인 정점을 큐에 넣는다. 그래프 아래에 있는 표는 진입차수를 나타낸 표이다. 

 

2. 큐에서 정점을 꺼내고 그 정점의 진출 간선을 찾아 인접한 곳의 진입차수를 1씩 감소시킨다.

3. 감소시킨 진입차수 중 0의 값을 가지고 있는 정점이 있으면 큐에 넣는다. 2와 5의 진입차수가 0이 되었으므로 큐에 넣었다. 

4. 위와 같은 과정을 반복하면 다음과 같다. 

 

 

 

 

👩‍💻 위상 정렬 구현 코드 

 

import java.util.*;

public class TopologicalSort{
	static int n, e;
    
    public static void main(String[] args){
    	n = 7; // 정점 개수
        e = 8; // 간선 개수
        
        int[] indegree = new int[n+1]; // 간선 개수 담는 배열
        ArrayList<Integer>[] graph = new ArrayList<>[n+1]; // 그래프 관계 표현
        
        for(int i=1; i<=n; i++){
            group[i] = new ArrayList<Integer>();
        }
        
        // 간선 목록 v1 -> v2
        int[] v1 = {1, 1, 2, 2, 5, 3, 6, 4};
        int[] v2 = {2, 5, 3, 6, 6, 4, 4, 7};
        
        // v1 -> v2 인접리스트 생성 
        // v2 요소의 각각 개수는 진입차수를 의미
        for(int i=0; i<e; i++;){
        	int c1 = v1[i];
            int c2 = v2[i];
           
            graph[c1].add(c2);
            indegree[c2]++; // 진입차수 증가 
        }
        
        topologicalSort(indegree, graph);
    }
    
    static void topologicalSort(int[] indegree, ArrayList<Integer>[] graph){
    	Queue<Integer> queue = new LinkedList<>();
       	Queue<Integer> result = new LinkedList<>();
        
        // 큐에 진입차수가 0인 노드 담기
        for(int i=0; i<n+1; i++){
        	if(indegree[i]==0) queue.add(i);
        }
        
        while(!queue.isEmpty()){
        	int node = queue.poll();
            result.add(node);
            
            for(Integer i : group[node]){
            	indegree[i]--;
                if(indegree[i]==0) queue.add(i);
            }
        }
        
        System.out.println(result);
    }
}

 

 

 

 

 

 

 

관련 문제 

https://arc.net/l/quote/rqqmbdep

2252번: 줄 세우기

 

https://www.acmicpc.net/problem/1516

1516번: 게임 개발