위상 정렬(Topology Sort)

1. 정의 🧊

위상 정렬

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

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

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

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

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

 

2. 동작 방식(BFS) 🥤

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

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

[동작 방식]

1. 진입 차수가 0인 정점을 Queue에 넣는다.
2. Queue에서 원소에 연결된 간선을 제거한다.
3. 간선이 제거가 된 후 진입 차수가 0이 된 정점을 Queue에 넣는다.
4. 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을 이용하면 경로를 쉽게 알 수 있지만 사이클 발생 여부를 알기 어렵다. 그래서 이번 글에서는 위상 정렬인지 아닌지를 쉽게 알아보기 위하여 진입차수와 방문여부를 사용하는 방식을 이용해 보자. (물론 이 방법도 경로를 확인할 수 있다.)

[동작 방식]

1. 진입 차수가 0인 정점을 먼저 방문한다.
2. DFS 방식을 이용하여 계속해서 다음 정점으로 진행한다.
   이때, 방문 여부를 표시해 준다.
3. 더 이상 진행할 수 없으면 방문 여부를 해제하면서 돌아온다.
4. 아직 방문하지 않은 진입차수 0인 정점들을 기준으로 1~3 과정을 반복한다.

  만약 2번의 과정에서 다음 정점이 이미 방문한 정점이라면 사이클이 발생하는 그래프이다. 즉, 위상 정렬이 불가능한 그래프이다.

  위상 정렬이 가능한 예시와 위상 정렬이 불가능한 예시를 통해 다시 한번 알아보자. 진행하면서 방문체크를 해주고 돌아오면서 방문 체크 해제하는 것을 잘 기억하자. 그러면 그림을 통해 쉽게 이해할 수 있을 거라고 생각한다. 

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

위상 정렬이 가능한 그래프

1번 경로 : 1 → 3 → 5 → 6

2번 경로 : 1 → 4 → 6

3번 경로 : 2 → 4 → 6

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

위상 정렬이 불가능한 그래프

  사이클이 존재하는 경우도 살펴보자. 위에서 언급한 것처럼 방문 표시가 된 곳을 재방문한다면 사이클이 발생하는 것이다. 

 

5. DFS를 이용한 구현 코드(JAVA) 🍷

  해당 방법의 입력 또한 정점의 개수와 간선의 개수를 받아오고, 간선의 개수만큼 출발 정점과 도착 정점을 나타낸다고 하자. 아래의 입력은 위상 정렬이 불가능한 그래프의 입력이다. (위상 정렬이 가능한 그래프의 입력은 BFS를 이용한 구현 코드에서 참고할 수 있다.)

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

public class TopologySortingByDFS {
	static int N, M;
	static Node[] adjNode;
	static boolean[] visited;
	static boolean isCycle;
	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];
		// 방문 체크 - 사이클 발생 여부를 확인하기 위한 것
		visited = new boolean[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]++;
		}
		
		topologySortByDFS();

		if(isCycle) {
			System.out.println("위상 정렬 불가능 (사이클 발생)");
		}
		else {
			System.out.println("위상 정렬 가능");
		}
	}

	static void topologySortByDFS(){
		
		for(int i = 1; i <= N; i++) {
			if(inDegree[i] == 0) {
				visited[i] = true;
				dfs(i);
				visited[i] = false;
			}
		}
	}
	
	static void dfs(int current) {
		
		// 마지막 정점인 경우
		if(adjNode[current] == null) {
			return;
		}

		for(Node temp = adjNode[current]; temp != null; temp = temp.link) {
			// 사이클이 발생하는 경우
			if(visited[temp.vertex]) {
				isCycle = true;
				return;
			}
			visited[temp.vertex] = true;
			dfs(temp.vertex);
			visited[temp.vertex] = false;
		}
	}
}

 

6. 시간복잡도 🧃

  위상 정렬을 할 때 '정점의 개수 + 간선의 개수'만큼 시간이 소요된다. 그러므로 위상 정렬의 시간 복잡도는 O(V  + E)이다.

 

해당 글은
나동빈님의 위상 정렬(Topology Sort)
yoongrammer님의 위상 정렬(Topological sort) 개념 및 구현
Topological Sorting using Kahn's Algorithm
을 참고하였습니다.