[알고리즘] 정렬(7) : 위상정렬 (Topological Sorting)

목차

1. 위상정렬의 개념

2. 위상정렬의 구현

3. 위상정렬 코드

 

개념

위상정렬은 방향이 있는 그래프에서 정점들 간의 선후 관계를 위배하지 않도록 정렬하는 방법입니다. 위상정렬에 대하여 설명하기 앞서 간단한 위상정렬의 예시에 대해 알아보겠습니다. 

 

위상 정렬은 선수과목이 있는 대학교의 커리큘럼을 생각하면 이해하기 쉽습니다. 다음과 같은 커리큘럼이 존재할 때 임베디드 시스템이라는 과목을 수강하기 위해서는 어떠한 순서로 과목을 수강해야 할까요?

 

 

여러가지 방법이 있겠지만 한 예시로 다음과 같은 수강 방법을 들 수 있습니다.

UNIX 시스템 → 어셈블리 언어 → 논리회로 설계 → 운영체제  → 컴퓨터 구조론 → 마이크로프로세서 → 임베디드 시스템

 

하지만 선수과목이 존재하기 때문에 다음과 같은 선후관계는 반드시 지켜져야 합니다. 따라서 운영체제를 먼저 듣고 어셈블리 언어를 나중에 듣는 것은 불가능합니다.  

 

위상 정렬을 수행한 모습은 위의 그림에서 볼 수 있듯이 왼쪽부터 오른쪽으로 일렬로 정점들을 나열했을 때 모든 간선들의 방향이 왼쪽에서 오른쪽으로 일정한 것을 볼 수 있습니다.

 

만일 사이클이 존재하거나 간선의 방향이 역행하는 구조 발생하는 경우는 위상 정렬이 불가능한 경우입니다.

 

위상정렬을 수행하기 위해서는 반드시 선행되어야 하는 필수 조건들이 몇가지 있습니다. 

1. 방향이 있는 그래프이어야만 한다.
2. 그래프에 사이클이 존재하지 않아야 한다.

위의 두 조건을 만족하는 그래프를 Directed Acyclic Graph 라고 하며 줄여서 DAG 라고 부릅니다. 

 

 

구현

위상정렬의 기본개념에 대해 알아보았습니다. 이제 본격적으로 위상정렬을 구현하는 방법에 대해서 알아보도록 하겠습니다. 

 

위상정렬을 구현하는 방법은 생각보다 간단합니다. 먼저 다음과 같은 그래프에서 위상정렬을 수행하는 과정을 살펴보도록 하겠습니다. 

 

 

 

 

 

코드

// 정점의 개수 
static int v; 

// 인접리스트
static List<Integer>[] adj;
// 해당 간선으로 들어오는 정점의 개수를 저장할 배열
static int[] indegree;

// 위상 정렬 결과를 저장할 리스트
static ArrayList<Integer> result = new ArrayList<>();


for(int i = 1; i<=n; i++) {
	adj[u].add(v):
    // 해당 정점으로 들어오는 간선인 경우 indegree 를 1증가
    indegree[v] += 1;
}

Queue<Integer> q = new LinkedList<>();

for(int i = 1; i<=n; i++) {
	if(indegree[i] == 0) q.add(i);
}

while(!q.isEmpty()) {
	int curr = q.poll();
    result.add(curr);
    for(int i = 0; i<adj[curr].size(); i++) {
    	int next = adj[curr].get(i);
        indegree[next] -= 1;
        if(indegree[next] == 0) q.add(next);
	}
}