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

 

위상 정렬(Topology Sort)

위키피디아: Topological sorting

 

 

위의 위키피디아 문서를 참조하면, 위상 정렬이란 정점의 선형 순서 지정을 통해 모든 방향 간선 uv에 대해 정점 u가 v보다 앞에 올 수 있게 정렬하기 위해 사용되는 알고리즘으로, 방향성 비순환 그래프 - DAG(Directed Acyclic Graph)에만 적용할 수 있다고 한다.

 

 

 

 

 

쉽게 말하자면 순서가 정해져 있는 작업을 차례로 수행해야할 때 순서를 결정해주는 알고리즘이고,

더 쉽게 말하자면, 순서를 찾아주는 알고리즘이다.

 

 

특징

나열한 정렬 순서만 두 가지 경우가 존재하고 추가로 여러 개의 답이 더 존재할 수 있다. 이처럼 위상 정렬은 여러 개의 답이 존재할 수 있다는 특징이 있다. 순회하는 방법이 한 가지보다 많을 수 있기 때문이다.

 

또한, 위에서 DAG에만 적용할 수 있다고 했다. 이 의미는, 시작점이 반드시 존재하는 사이클이 없는 그래프를 뜻한다. 즉 특정 정점 하나 이상은 반드시 가리키는 대상이 되어서는 안된다. 다시말해 진입 차수가 0이어야만 한다.

 

 

동작 과정

위상 정렬은 다음과 같은 과정을 통해 위상 정렬 가능 여부와, 위상 정렬의 결과를 반환한다.

 

1. 진입 차수가 0인 정점을 스택 / 큐에 삽입한다.

2. 원소를 스택 / 큐에서 꺼내 연결된 모든 간선을 제거한다.

 

1~2번의 과정을 반복하면서, 위상 정렬을 진행한다.

 

정점의 개수만큼 반복이 올바르게 동작한다면 위상 정렬이 가능한 것이며 올바른 위상 정렬 결과를 반환하게 된다. 반대로 모든 정점을 순회하지 못한다면 위상 정렬을 올바르게 수행하지 못한 것이다. 올바른 그래프 구조라고 했을 때, 사이클이 발생한다는 것이다.

 

 

필자는 P.S. 문제에서 bfs와 더불어 위상 정렬이 필요한 경우가 많았기 때문에 자연스레 큐로 구현한다.

위의 출근 그래프를 가지고 위상 정렬을 수행해보자.

 

 

 

이 때, 8번 그림과 같이 5번 정점의 진입차수는 1이기 때문에, 큐에 삽입하지 않는다.

 

 

 

 

 

 

 

 

 

 

 

코드(Java)

원리도 알았고, 동작 과정도 그림으로 표현해봤으니 코드로 작성해보자.

public class Main {
	public static void main(String[] args) {
    	int TOTAL_NODE = 10;
        
        //진입 차수 배열
    	int[] degree = new int[TOTAL_NODE + 1];
        //그래프 정보
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= TOTAL_NODE; i ++) {
        	graph.add(new ArrayList<>());
        }
        
        graph.get(1).add(2);
        graph.get(1).add(7);
        graph.get(2).add(3);
        graph.get(2).add(4);
        graph.get(3).add(5);
        graph.get(4).add(5);
        graph.get(5).add(6);
        graph.get(6).add(9);
        graph.get(7).add(8);
        graph.get(8).add(9);
        graph.get(9).add(10);
        
        degree[2] = 1;
        degree[3] = 1;
        degree[4] = 1;
        degree[5] = 2;
        degree[6] = 1;
        degree[7] = 1;
        degree[8] = 1;
        degree[9] = 2;
        degree[10] = 1;
        
        topologySort(TOTAL_NODE, degree, graph);
    }
    
    public static void topologySort(int N, int[] degree, List<List<Integer>> graph) {
    	Queue<Integer> que = new LinkedList<>();
        int pollCnt = 0;
        
        //진입차수가 0인 정점을 큐에 삽입한다.
        for (int i = 1; i <= N; i ++) {
        	if (degree[i] == 0) que.offer(i);
        }
        
        while(!que.isEmpty()) {
        	//큐에서 원소를 뺀다.
        	int V = que.poll();
            pollCnt++;
           
            //간선을 제거하고 진입차수가 0인 정점을 큐에 삽입한다.
            for (int next: graph.get(V)) {
            	if (--degree[next] == 0) que.offer(next);
            }
        }
        
        //정점의 개수보다 큐에 삽입된 원소가 작다면, 사이클이 발생한 것이다.
        if (pollCnt < N) {
        	System.out.println("CYCLE");
        }
    }
}

 

 

 

 

 

참조

https://en.wikipedia.org/wiki/Topological_sorting

Topological sorting - Wikipedia

 

https://www.geeksforgeeks.org/topological-sorting/

Topological Sorting - GeeksforGeeks