정렬을 떠올릴 때 보통 배열과 같이 일련의 원소에 대한 정렬을 생각하곤 한다.
그러나 특정한 그래프에서는 순차적인 처리가 요구되는 경우가 있다.
따라서 이번 포스팅에서는 그래프를 정렬하는 위상 정렬에 대하여 알아볼 것이다.
작업의 순서를 정렬할 때 여러가지 경우의 수가 나올 수 있다. 그 이유는 각각의 독립된 작업의 경우 그 순서가 바뀌어도 상관이 없기 때문이다.
예를 들자면 1번 작업을 완료한 경우 2,3,4,5번 작업을 완료할 경우 그 순서는 (3,4,2,5), (2,5,3,4), (2,3,4,5), (2,3,5,4) 등 여러 가지가 있다.
이제 위상 정렬을 구현할 때 사용되는 대표적인 방법을 소개하겠다.
바로 각 노드들에 indegree를 이용하는 것이다.
indegree란 특정 노드에 대해서 다른 노드로부터 들어오는 간선의 개수를 뜻한다.
간단한 예시로 위 그림에서 노드 6에 대한 indegree는 2가 된다. (노드 4,5로부터 들어가는 간선)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/86f0f86f-ec92-4574-aa90-d2cdf6e6d760.png)
2)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/1e014f4a-07f5-4181-bfc0-50eae32f17ad.png)
3)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/2b42c1d4-debf-4690-8189-256a26ca89ae.png)
4)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/71350df3-431c-457e-844f-6d1656a4874d.png)
그러나 특정한 그래프에서는 순차적인 처리가 요구되는 경우가 있다.
따라서 이번 포스팅에서는 그래프를 정렬하는 위상 정렬에 대하여 알아볼 것이다.
DAG (Directed Acyclic Graph)
그래프는 유향 그래프와 무향 그래프로 나눌 수 있다.
또한 그래프는 순환 그래프가 있고 비순환 그래프가 있다.
DAG는 이름에도 알 수 있다시피 유향 그래프이면서 순환이 존재하지 않는 그래프라 할 수 있다.
DAG는 노드들간에 명확한 순서가 존재하므로 위상 정렬을 수행할 수 있다.
위상 정렬 (Topological sort)
위상 정렬을 설명하기 위해 간단한 DAG를 아래의 그림으로 예시를 들었다.
위 그래프의 노드는 각각의 작업이며 그래프는 작업의 순서를 나타낸다고 생각해보자.
- 1번 작업을 수행해야 2,3번 작업을 수행할 수 있다.
- 2번 작업을 수행하면 5번 작업을 수행할 수 있다.
- 3번 작업을 수행하면 4번 작업을 수행할 수 있다.
- 4,5번 작업을 모두 수행하면 6번 작업을 수행할 수 있다.
작업의 순서를 정렬할 때 여러가지 경우의 수가 나올 수 있다. 그 이유는 각각의 독립된 작업의 경우 그 순서가 바뀌어도 상관이 없기 때문이다.
예를 들자면 1번 작업을 완료한 경우 2,3,4,5번 작업을 완료할 경우 그 순서는 (3,4,2,5), (2,5,3,4), (2,3,4,5), (2,3,5,4) 등 여러 가지가 있다.
위상 정렬 구현
이제 위상 정렬을 구현할 때 사용되는 대표적인 방법을 소개하겠다.
바로 각 노드들에 indegree를 이용하는 것이다.
indegree란 특정 노드에 대해서 다른 노드로부터 들어오는 간선의 개수를 뜻한다.
간단한 예시로 위 그림에서 노드 6에 대한 indegree는 2가 된다. (노드 4,5로부터 들어가는 간선)
로직
- DAG의 각 노드들의 indegree를 저장
- 방문하지 않은 노드들 중 indegree가 0인 노드들을 찾는다.
- 해당 노드들을 방문 체크 후 해당 노드들의 진출 간선과 연결된 다른 노드들의 indegree를 감소한다.
- DAG의 모든 노드들이 탐색될 때까지 2,3번 과정을 반복한다.
예시
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/86f0f86f-ec92-4574-aa90-d2cdf6e6d760.png)
2)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/1e014f4a-07f5-4181-bfc0-50eae32f17ad.png)
3)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/2b42c1d4-debf-4690-8189-256a26ca89ae.png)
4)
![](https://bcw2104.cdn3.cafe24.com/resources/upload/files/post/34/inner/71350df3-431c-457e-844f-6d1656a4874d.png)
댓글