정렬을 떠올릴 때 보통 배열과 같이 일련의 원소에 대한 정렬을 생각하곤 한다.
그러나 특정한 그래프에서는 순차적인 처리가 요구되는 경우가 있다.
따라서 이번 포스팅에서는 그래프를 정렬하는 위상 정렬에 대하여 알아볼 것이다.
작업의 순서를 정렬할 때 여러가지 경우의 수가 나올 수 있다. 그 이유는 각각의 독립된 작업의 경우 그 순서가 바뀌어도 상관이 없기 때문이다.
예를 들자면 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로부터 들어가는 간선)
2)
3)
4)
그러나 특정한 그래프에서는 순차적인 처리가 요구되는 경우가 있다.
따라서 이번 포스팅에서는 그래프를 정렬하는 위상 정렬에 대하여 알아볼 것이다.
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번 과정을 반복한다.
예시
2)
3)
4)
댓글