위상 정렬(Topological Sort)

이번에 배워볼 알고리즘은 위상 정렬(Topological Sort) 알고리즘이다. 위상 정렬은 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해 주는 알고리즘이다.

간단한 예시를 들어본다면 라면을 끓이기 위해서는 물이 먼저 끓어야 한다. 이처럼 작업의 순서가 정해져 있는 그래프에서 작업의 순서를 정렬해 주는 알고리즘이다.

​단, 위상 정렬은 DAG에서만 적용이 가능하다. DAG는 Directed Acyclic Graph의 줄임말로써 방향 사이클이 없는 방향 그래프를 뜻한다. 왜냐하면 방향 사이클이 존재한다면 시작 지점을 정할 수 없기 때문이다.

위와 같은 그래프는 DAG가 아니다. 1-2-3-1로 이루어지는 방향 사이클이 존재하기 때문이다. 1번 작업을 수행하기 위해선 3번 작업이 먼저 수행되어야 하고, 3번 작업을 수행하기 위해선 2번 작업이 먼저 수행되어야 하고, 2번 작업을 수행하기 위해선 1번 작업이 먼저 수행되어야 한다. 이처럼 작업의 순서를 매길 수가 없기 때문에 DAG에서는 위상 정렬을 수행할 수 없다.

​

이전에 그래프 자료구조를 배울 때 진입 차수(in-Degree)와 진출 차수(out-Degree)를 배웠다. 정점 A에서의 진입 차수는 정점 A가 수행되기 전에 먼저 수행되어야 할 정점의 개수를 뜻한다. 반대로 진출 차수는 정점 A가 먼저 수행되어야 수행할 수 있는 정점의 개수를 뜻한다.

​위상 정렬을 구현하는 방법은 DFS(진출 차수)를 이용하는 방법과 BFS(진입 차수)를 이용하는 방법이 존재한다. 먼저 DFS를 이용하여 위상 정렬을 구현하는 방법을 알아보자.

​

DFS를 이용한 위상 정렬의 동작 원리는 다음과 같다.

• 임의의 방문하지 않은 한 정점을 잡고 DFS를 수행하면서 방문하는 정점들을 스택에 담는다.
• 모든 정점의 방문될 때까지 1번을 반복한다.
• 모든 정점을 방문했다면 스택에 담긴 정점들을 출력한다.

​

DFS는 깊이를 우선시하는 탐색 방법이었던 것을 기억해라. 결국 한 정점에서 DFS를 수행하게 되면 말단 노드까지 내려갈 것이다. 말단 노드는 진출 차수가 0이기 때문에 가장 마지막에 수행되어야 하는 작업을 뜻하게 된다.

그렇다면 말단 노드부터 DFS 역순으로 출력을 하게 된다면 가장 늦게 해야 할 작업의 순서부터 차례대로 출력이 될 것이다. LIFO 형태의 스택을 이용한다면 가장 먼저 해야 할 작업부터 가장 늦게 해야 할 작업의 순서로 출력을 쉽게 할 수 있다.

또한, 임의의 방문하지 않은 정점을 선택해도 상관이 없는 이유는 DFS는 선택한 정점보다 늦게 수행되어야 할 정점(더 깊은 정점)들만 방문하는 원리이기 때문이다.

​마지막으로 DAG인지 확인하기 위해 사이클의 유무를 판단할 수 있어야 한다. 우리는 DFS를 수행할 때 정점을 방문하게 되면 방문 표시를 해준다.

만약 방문 표시가 돼있는데 아직 끝나지 않은 정점을 DFS 호출 도중 보게 된다면 이는 사이클이 존재한다는 것을 뜻하게 된다. 이를 위해 finish라는 배열을 따로 생성하여 DFS가 완전히 끝날 때 표시를 하여 사이클의 유무를 판단한다.

​

그럼 DFS를 이용한 위상 정렬의 동작 과정을 그림으로 살펴보자.

 

먼저 방문하지 않은 임의의 정점을 선택한다. 나는 정점 B를 선택하겠다. 정점 B에서 DFS를 수행하게 되면 먼저 정점 E를 방문하게 된다. 정점 E에서 더 이상 방문할 정점이 존재하지 않기 때문에 정점 E를 스택에 담아준다.

 

정점 B에서 정점 F를 방문하고 더 이상 방문할 정점이 존재하지 않기 때문에 정점 F를 스택에 담아준다. 정점 B 또한 더 이상 방문할 곳이 존재하지 않기 때문에 스택에 담아준다.

 

다음으로 방문하지 않은 정점 A에서 DFS를 수행한다. A-C-G 순서로 방문하게 되고 정점 G에서 더 이상 방문할 정점이 존재하지 않기 때문에 정점 G를 스택에 담아준다. 정점 C 또한 마찬가지로 스택에 담아준다.

 

마지막으로 정점 D를 방문 후 스택에 담아주고 정점 A 역시 스택에 담아준다.

 

DFS를 이용한 위상 정렬의 최종 결과는 스택에서 차례대로 출력한 A-D-C-G-B-F-E 순서이다. DFS를 이용한 위상 정렬은 O(V+E)의 시간 복잡도를 가진다. DFS의 시간 복잡도를 생각하면 될 것이다.

​

DFS를 이용한 위상 정렬을 Java로 구현한 코드는 다음과 같다.

import java.util.ArrayList;
import java.util.Stack;

class MyGraph {
	int vertexCnt;
	ArrayList<Integer>[] edge_List;
	boolean[] visit;
	boolean[] finish;
	Stack<Integer> answer;
	boolean cycle;
	
	public MyGraph(int N) {
		this.vertexCnt = N;
		edge_List = new ArrayList[N+1];
		for (int i = 0; i <= N; ++i) {
			edge_List[i] = new ArrayList<>();
		}
		visit = new boolean[vertexCnt+1]; //방문 표시
		finish = new boolean[vertexCnt+1]; //사이클 판단
		answer = new Stack<>(); //결과를 담을 스택
	}

	public void insert_Edge(int from, int to) {
		edge_List[from].add(to);
	}

	public void topological_Sort() {
		//방문하지 않은 정점을 DFS 수행
		for (int i = 1; i <= vertexCnt; ++i) {
			if (cycle) {
				System.out.println("그래프에 사이클 존재");
				return;
			}
			if (!visit[i]) {
				dfs(i);
			}
		}
		
		//스택에 담긴 정점들을 출력
		while (!answer.isEmpty()) {
			System.out.print(answer.pop() + " ");
		}
	}
	
	public void dfs(int v) {
		visit[v] = true;
	
		for (int i = 0; i < edge_List[v].size(); ++i) {
			int nv = edge_List[v].get(i);
			
			//방문하지 않았으면 dfs 수행
			if (!visit[nv]) {
				dfs(nv);
			} 
			//방문한 정점인데 finish 체크가 되지 않았으면 사이클이 존재한다는 의미
			else if (!finish[nv]) {
				cycle = true;
				return;
			}
		}
		
		//더 이상 갈 곳이 없는 정점을 finish 체크 & 스택에 넣어줌 (말단부터 상위로)
		finish[v] = true;
		answer.push(v);
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(7);
		mg.insert_Edge(1, 2);
		mg.insert_Edge(1, 3);
		mg.insert_Edge(1, 4);
		mg.insert_Edge(2, 5);
		mg.insert_Edge(2, 6);
		mg.insert_Edge(3, 7);
		mg.insert_Edge(3, 6);
		mg.insert_Edge(4, 3);
		mg.insert_Edge(6, 5);
		mg.topological_Sort();
	}
}

 

이번에는 BFS를 이용한 위상 정렬을 살펴보자. BFS를 이용한 위상 정렬의 동작 원리는 다음과 같다.

• 진입 차수가 0인 시작 정점 한 개를 큐에 담아준다.
• 큐가 비어있지 않다면 정점 한 개를 뽑아서 리스트에 담아준다. 만약 큐가 비었다면 종료한다.
• 뽑아낸 정점에 인접한 모든 정점의 진입 차수를 -1만큼 감소시킨다. 이때 감소한 진입 차수가 0이라면 이 정점은 새로운 시작점이 될 수 있는 정점이기 때문에 큐에 담아준다.

​

위 2, 3번 과정을 큐가 빌 때까지 반복하면 된다. BFS를 이용한 위상 정렬도 마찬가지로 사이클의 존재 유무를 판단해야 한다.

DFS는 동작 과정에서 사이클의 유무를 판단했다면 BFS는 최종 결과에서 사이클의 유무를 판단한다. 큐에 더 이상 정점이 없어서 종료되면 결과를 담아놓은 리스트의 크기를 확인한다. 만약 리스트의 크기가 정점의 수보다 적다면 이는 사이클이 존재하여 위상 정렬이 제대로 수행되지 않았음을 알 수 있다.

​

그럼 BFS를 이용한 위상 정렬의 동작 과정을 그림으로 살펴보자.

 

BFS는 DFS와 다르게 임의의 정점에서 시작하는 것이 아니라 진입 차수가 0인 정점부터 시작해야 한다. 그렇기 때문에 시작하기에 앞서 모든 정점의 진입 차수 개수를 초기화해줘야 한다. 1차원 배열을 선언해서 진입 차수 개수를 관리해 주도록 하자. 위 그래프에서 진입 차수가 0인 정점은 A 한 개이기 때문에 A를 큐에 담아준다.

 

큐에서 정점 A를 뽑아낸다. 정점 A에 인접한 B, C, D 정점의 진입 차수를 1만큼 감소시킨다. 정점 A는 최종 결과를 담는 리스트에 담아준다.

 

정점 B, D의 진입 차수가 0이기 때문에 큐에 담아준다.

 

큐에서 정점 B를 뽑아낸다. 정점 B에 인접한 E, F 정점의 진입 차수를 1만큼 감소시킨다. 정점 B는 최종 결과를 담는 리스트에 담아준다.

진입 차수가 0인 정점이 없기 때문에 큐에서 정점 D를 뽑아낸다. 정점 D에 인접한 C 정점의 진입 차수를 1만큼 감소시킨다. 정점 D는 최종 결과를 담는 리스트에 담아준다.

 

정점 C의 진입 차수가 0이기 때문에 큐에 담아준다.

 

큐에서 정점 C를 뽑아낸다. 정점 C에 인접한 F, G 정점의 진입 차수를 1만큼 감소시킨다. 정점 C는 최종 결과를 담는 리스트에 담아준다.

 

정점 F, G의 진입 차수가 0이기 때문에 큐에 담아준다.

 

큐에서 정점 F를 뽑아낸다. 정점 F에 인접한 E 정점의 진입 차수를 1만큼 감소시킨다. 정점 F는 최종 결과를 담는 리스트에 담아준다.

 

정점 E의 진입 차수가 0이기 때문에 큐에 담아준다.

 

큐에서 정점 G를 뽑아낸다. 정점 G에 인접한 정점이 없기 때문에 바로 결과 리스트에 담아준다. 또한 정점 E도 인접한 정점이 없기 때문에 결과 리스트에 담아준다.

 

BFS를 이용한 위상 정렬의 최종 결과는 A-B-D-C-F-G-E 순서이다. 위상 정렬은 정답이 유일한 것이 아님을 주의해라. DFS를 이용한 위상 정렬의 결과는 A-D-C-G-B-F-E 순서였다.

방문하는 순서에 따라 결과는 다양하게 나올 수가 있기 때문에 최종 결과는 위의 그래프에서 나올 수 있는 정답 중 한 가지일 뿐이다. BFS를 이용한 위상 정렬 또한 O(V+E)의 시간 복잡도를 가진다. BFS의 시간 복잡도를 생각하면 될 것이다.

​

BFS를 이용한 위상 정렬을 Java로 구현한 코드는 다음과 같다.

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

class MyGraph {
	int vertexCnt;
	int[] in_Degree;
	ArrayList<Integer>[] edge_List;
	
	public MyGraph(int N) {
		this.vertexCnt = N;
		edge_List = new ArrayList[N+1];
		for (int i = 0; i <= N; ++i) {
			edge_List[i] = new ArrayList<>();
		}
		in_Degree = new int[vertexCnt+1];
	}

	public void insert_Edge(int from, int to) {
		edge_List[from].add(to);

		//to의 진입 차수 증가
		in_Degree[to]++;
	}

	public void topological_Sort_BFS() {
		Queue<Integer> q = new LinkedList<>();
		
		//진입 차수가 0인 정점들을 큐에 넣어줌
		for (int i = 1; i <= vertexCnt; ++i) {
			if (in_Degree[i] == 0) {
				q.offer(i);
			}
		}
		
		//결과의 크기는 정점의 수여야 하기 떄문에 정점의 수만큼 반복 
		for (int i = 1; i <= vertexCnt; ++i) {
			//다 돌기전에 큐가 비었다는 것은 사이클이 존재한다는 것을 의미
			if (q.isEmpty()) {
				System.out.println("그래프에 사이클이 존재");
				return;
			}
			
			int v = q.poll();
			System.out.print(v + " ");
			
			for (int j = 0; j < edge_List[v].size(); ++j) {
				int nv = edge_List[v].get(j);
				
				//인접한 정점의 진입 차수를 -1만큼 감소하고 0이면 큐에 넣어준다.
				if (--in_Degree[nv] == 0) {
					q.offer(nv);
				}
			}
		}
	}
}

public class Blog {

	public static void main(String[] args) {
		MyGraph mg = new MyGraph(7);
		mg.insert_Edge(1, 2);
		mg.insert_Edge(1, 3);
		mg.insert_Edge(1, 4);
		mg.insert_Edge(2, 5);
		mg.insert_Edge(2, 6);
		mg.insert_Edge(3, 7);
		mg.insert_Edge(3, 6);
		mg.insert_Edge(4, 3);
		mg.insert_Edge(6, 5);
		mg.topological_Sort_BFS();
	}
}