위상 정렬(Topology Sort)

1. 정의 🧊

위상 정렬(Topology Sort)이란 순서가 정해져 있는 작업을 차례대로 수행할 때 그 순서를 결정해 주는 알고리즘이다.

교육과정의 선수과목이 위상 정렬을 설명하는 가장 적절한 예시이다. 컴퓨터 공학을 전공하고 있는 학생은 다음 전공과목(ex. 알고리즘)을 듣기 위해서는 선수 과목(ex. 자료구조)을 필수적으로 들어야 한다.

기초컴퓨터프로그래밍 → 자료구조 → 알고리즘
자료구조 → 논리회로및설계 → 논리회로실험
알고리즘 → 논리회로및설계 → 논리회로실험

또한, 위상정렬은 위와 같이 여러 개의 경로가 존재할 수 있다.

마지막 특징으로는 위상 정렬은 비순환 유향 그래프(DAG - Directed Acyclic Graph)에만 적용이 가능하다. 즉, 사이클이 발생하지 않는 방향 그래프여야 한다.

2. 동작 방식(BFS) 🥤

위상 정렬은 BFS와 DFS를 통해 구현할 수 있다. 우선 BFS를 이용하는 방법을 먼저 알아보자.

BFS를 이용하는 경우 진입 차수와 Queue를 활용한다. 동작 방식은 아래와 같다.

[동작 방식]

진입 차수가 0인 정점을 Queue에 넣는다.
Queue에서 원소에 연결된 간선을 제거한다.
간선이 제거가 된 후 진입 차수가 0이 된 정점을 Queue에 넣는다.
Queue가 빌 때까지 2번과 3번을 반복한다.

작업이 끝난 후 모든 정점을 방문했다면 위상 정렬이 가능한 그래프이고 그렇지 못한 상황은 사이클이 존재하는 경우이다. 아래의 위상 정렬이 가능한 예시와 위상 정렬이 불가능한 예시를 통해 한번 더 이해를 살펴보자.

[위상 정렬이 가능한 예시]

정점	1	2	3	4	5	6
진입 차수	0	0	1	2	1	2

정점	1	2	3	4	5	6
진입 차수	방문	방문	0	0	1	2

정점	1	2	3	4	5	6
진입 차수	방문	방문	방문	방문	0	1

정점	1	2	3	4	5	6
진입 차수	방문	방문	방문	방문	방문	0

정점	1	2	3	4	5	6
진입 차수	방문	방문	방문	방문	방문	방문

[위상 정렬이 불가능한 예시]

정점	1	2	3	4	5	6
진입 차수	0	0	2	3	1	1

정점	1	2	3	4	5	6
진입 차수	방문	방문	1	1	1	1

사이클이 있으면 아직 방문을 하지 못했지만 정점들의 진입 차수가 0이 아니라서 더 이상 방문을 하지 못하는 상황이 발생한다. 즉, 모든 정점을 방문하지 못한 경우는 사이클이 있어서 위상 정렬이 불가능한 상황이라고 할 수 있다.

3. BFS를 이용한 구현 코드 (JAVA) 🍹

첫 줄에는 정점의 개수와 간선의 개수를 받아온다. 그리고 간선의 개수만큼 출발 정점과 도착 정점들을 보여준다. 아래는 위에서 살펴본 예시를 입력으로 나타낸 것이다.

6 6
1 3
1 4
2 4
3 5
4 6
5 6

public class TopologySorting {
	static int N, M;
	static Node[] adjNode;
	static int[] inDegree;

	static class Node {
		int vertex;
		Node link;

		public Node(int vertex, Node link) {
			super();
			this.vertex = vertex;
			this.link = link;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		// 인접 리스트
		adjNode = new Node[N + 1];
		// 진입 차수
		inDegree = new int[N + 1];
		int from, to;

		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			from = Integer.parseInt(st.nextToken());
			to = Integer.parseInt(st.nextToken());
			// 인접 리스트 추가
			adjNode[from] = new Node(to, adjNode[from]);
			// 진입 차수 추가
			inDegree[to]++;
		}

		// 위상 정렬을 통해 얻어진 경로를
		// resultFromTopologySort에 저장
		ArrayList<Integer> resultFromTopologySort = topologySortByBFS();
		
		if(resultFromTopologySort.size() == N) {
			System.out.println("위상 정렬 가능");
			for(Integer i : resultFromTopologySort) {
				System.out.print(i + " ");
			}
		}
		else {
			System.out.println("위상 정렬 불가능 (사이클 발생)");
		}
	}

	static ArrayList<Integer> topologySortByBFS(){
		Queue<Integer> queue = new ArrayDeque<>();
		// 진입차수가 0인 정점 추가
		for(int i = 1; i <= N; i++) {
			if(inDegree[i] == 0)
				queue.offer(i);
		}

		ArrayList<Integer> visitedNode = new ArrayList<>();
		while(!queue.isEmpty()) {
			int currentNode = queue.poll();
			visitedNode.add(currentNode);

			for(Node temp = adjNode[currentNode]; temp != null; temp = temp.link) {
				// 연결된 간선을 제거해주는 행위
				inDegree[temp.vertex]--;
				
				// 진입 차수가 0이 된 경우
				if(inDegree[temp.vertex] == 0) {
					queue.offer(temp.vertex);
				}
			}
		}

		return visitedNode;
	}
}

4. 동작 방식(DFS) 🍸

DFS를 이용하는 경우 진입 차수와 방문 여부를 활용한다. DFS의 경우 Stack을 이용하는 방법도 있다. Stack을 이용하면 경로를 쉽게 알 수 있지만 사이클 발생 여부를 알기 어렵다. 그래서 이번 글에서는 위상 정렬인지 아닌지를 쉽게 알아보기 위하여 진입차수와 방문여부를 사용하는 방식을 이용해 보자. (물론 이 방법도 경로를 확인할 수 있다.)