위상 정렬

 

1. 위상 정렬 알고리즘

 

 

그래프와 관련된 알고리즘이다.

선후 관계가 정의된 구조에서 정렬을 하기 위해 사용된다.

 

 

1) 예제로 설명

 

5가지 업무가 있다고 하자.

그런데 이 업무에는 우선순위가 있어서

 

아래와 같이 각 줄에 주어진 순서대로 업무가 진행되어야 한다.

 

 

• 1 2
• 3 5 1
• 3 4
• 4 1

 

 

이때 5가지 업무를 어떤 순서로 진행해야

위에 주어진 우선순위를 만족할지 

구하는 것이 위상 정렬 알고리즘이다.

 

2) 조건

 

 

• 방향성이 있어야 한다.
• 사이클이 없는 그래프여야 한다.

 

 

3) 그림으로 설명

 

위의 상황을 그래프로 표현하면 다음과 같다.

사이클도 없고 방향성도 있다.

 

 

이때 사용되는 배열이 있다. => value 배열

진입차수를 나타내는 배열이다. 즉 특정한 노드로 들어오는 간선의 개수를 나타낸다.

예를 들어서 위에서 노드 1은 노드 4, 5가 가리키고 있다. 즉 간선이 2개로,

 value[1] = 2 가 된다.

 

즉, 초기에는 다음과 같다.

 

 

위상 정렬 알고리즘을 단계별로 살펴보자.

 

과정

 

value 배열값이 0 인 노드를 큐에 넣어준다.

=> 처음에는 노드 3이 된다.

 

큐에서 노드를 하나 꺼낸 후 이 노드와 연결된 노드들의 value 배열값을 1씩 감소시킨다.

=> 3과 연결된 노드는 4,5가 있으므로 value[4], value[5] 값이 1씩 감소한다.

 

이때 value[4]나 value[5] 가 0이 되면 우선순위 큐에 넣어준다.

 

큐에 아무 값도 없을 때까지 위의 과정을 반복한다.

 

 

단계 1

 

1. 처음에 value 배열값이 0인 노드 3을 큐에 넣어준다.

 

 

 

단계 2

 

1. 큐에서 노드 3을 꺼낸 후 3과 연결된 노드, 즉 4와 5의 value 배열값을 1씩 감소시킨다.

 

 

 

2. 이는 3번 노드의 간선이 제거되는 것과 같은 의미이므로 그래프에서 간선을 지우고 노드 3의 색깔도 흰색으로 바꿔주었다.

 

 

 

 

3. 이 과정은 5가지 업무를 어떤 순서로 진행할지 결정하는 것인데,

큐에서 나온 순서가 결과가 된다.

따라서 맨 처음 업무 순서는 3이다.

 

 

 

4. 

4,5번 노드의 value 배열값이 0인지 확인합니다. 0이라면 큐에 넣어주고, 아니면 다음 순서로 넘어간다.

4,5번 노드의 value 배열값이 0이므로 큐에 넣어준다.

이때 어떤 노드가 먼저 큐에 들어가던지 상관없다.

5부터 넣고 4를 넣는다.

 

 

 

단계 3

 

1. 큐에서 5를 꺼내고 5와 연결된 노드.1의 value 값을 1 줄인다.

 

 

 

2.

5번 노드의 간선이 제거되는 것과 같은 의미이므로 간선을 지우고 노드 5의 색깔을 흰색으로 바꿔준다.

 

 

3. 업무 순서는 다음과 같다.

 

 

 

4.

1번 노드의 value 값이 0 이 아니다. 그러므로 큐에 넣지 않고 다음으로 넘어간다.

 

그러면 큐에는 4만 남아있게 된다. 

 

 

 

 

단계 4

 

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

 

1. 큐에서 4를 꺼낸다.

 

2. 4와 연결된 노드 1의 value 값을 감소시킨다.

 

 

3. 

 

 

 

4. 

 

 

5. 1번 노드의 value 배열 값이 0 이다.

큐에 1번 노드를 넣는다.

 

 

 

단계 5

 

1. 큐에서 1을 꺼낸다.

 

2. 노드 1과 연결된 노드 2의 value 값을 감소시킨다.

 

 

 

3.

 

 

4. 

 

 

 

5.

2번 노드의 value 값이 0 이다.

큐에 2번 노드를 넣는다.

 

 

 

단계 6

 

1. 큐에서 2를 꺼낸다.

 

2. 노드 2와 연결된 노드가 없으므로 value 배열은 그대로이다.

 

 

 

3.

노드 2와 연결된 노드가 없었고, 그래서 제거할 간선도 없다. 이전 상태와 동일하다.

 

 

 

4. 큐에서 노드 2를 꺼냈으므로 순서가 정해진다.

 

 

과정이 끝났다.

 

4) 결론

 

 

이 결과를 보면 예제에서 요구한 업무 우선순위를 만족함을 알 수 있다.

 

• 1 2
• 3 5 1
• 3 4
• 4 1

 

그런데 단계 2에서 노드 4,5를 큐에 넣을 때 

4,5순이나, 5,4 순이나 상관없다고 했다.

그래서 5부터 넣었다.

 

하지만 만약 4,5 순서대로 큐에 넣었다면

결과는 3 4 5 1 2 가 되었을 것이다.

 

그런데 이 순서도 업무 우선순위를 만족한다.

그래서 큐에 4를 먼저 넣던지 5를 먼저 넣던지 상관없다.

 

아래 코드에서 위상정렬 알고리즘 메소드는 solve 메소드에 나타내었다.

 

2. 최종 코드

 

import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static int value[];
	static ArrayList<ArrayList<Integer>> input;
	static int n;
	static Queue<Integer> result ;
	
	public static void main(String[] args) throws IOException {
		
		n = 5;
		value = new int[n+1];
		result = new LinkedList<>();
		input = new ArrayList<>();
		
		for(int i=0; i<n+1; i++) {
			input.add(new ArrayList<>());
		}
		
		input.get(1).add(2);
		input.get(3).add(5);
		input.get(5).add(1);
		input.get(3).add(4);
		input.get(4).add(1);
		
		value[1] = 2;
		value[2] = 1;
		value[3] = 0;
		value[4] = 1;
		value[5] = 1;
		
		solve();
		
		while(!result.isEmpty()) {
			System.out.print(result.poll()+ " " );
		}
	
	}
	
	public static void solve() {
		
		Queue<Integer> queue = new LinkedList<>();
	
		for(int i =1; i<n+1; i++) {
			if(value[i] ==0) {
				queue.add(i);
			}
		}
		
		while(!queue.isEmpty()) {
			
			int a= queue.poll();
			result.add(a);
			
			for(int i=0; i<input.get(a).size(); i++) {
				
				int b = input.get(a).get(i);
				value[b]--;
				
				if(value[b] ==0) {
					queue.add(b);
				}
				
			}	
		}
	}
}

 

 

참고 자료 :

https://bcp0109.tistory.com/21

위상정렬 Topological Sort (Java)

https://codingnojam.tistory.com/66

[Algorithm] 위상정렬(Topological Sort)을 Java로 구현해보자!!

https://devfunny.tistory.com/661

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