위상 정렬을 구하는 두 가지 방법

 

---

위상 정렬이란

다음과 같은 그래프가 있다

각 노드는 해야할 작업이며

작업은 이전 작업이 끝나야 시작할 수 있다

 

예를 들어

3번 작업을 하기 위해서는 2번 작업을 먼저 해야하고

2번 작업을 하기 위해서는 1번 작업을 먼저해야한다

그러므로 작업순서는 1 2 3이 된다

 

그러면 다음과 같은 경우를 보자

3번이나 5번 작업을 하기 위해서는 2번 작업을 먼저 해야하고

2번 작업을 하기 위해서는 1번과 4번 작업을 해야한다

그러므로 작업 순서는 1 4 2 3 5 or 4 1 2 3 5 or 1 4 2 5 3 or 4 1 2 5 3 이 될 수 있다

 

이처럼 작업 순서가 있는 경우 작업 순서를 구하는 것을 위상 정렬이라 한다

 

위상 정렬하는 방법

위상 정렬을 구하는 방법에는 두 가지가 있다

1. 진입 차수가 0인 노드를 지우면서 출력하기
2. 방향을 바꾸고 DFS를 돌리면서 출력하기

 

1. 진입 차수가 0인 노드를 지우면서 출력하기

그래프에서는 진입 차수와 진출 차수가 있다

진입 차수는 자신에게 들어오는 간선의 개수이고

진출 차수는 다른 노드에게 가는 간선의 개수이다

 

다음 예제에서 진입 차수가 0인 노드를 지우면서 출력을 해보자

 

현재 진입 차수가 0인 노드는 1과 4이다

둘 중 하나를 지우면서 출력한다

 

현재 집입 차수가 0인 노드는 4이다

4를 지우면서 출력한다

이 과정을 반복하면

다음에는 2를 지우고

다음에는 3이나 5를 지우게 된다

진입 차수가 0인 노드가 여러개 있을 때

어떤 노드를 먼저 지우느냐에 따라서 작업순서가 달라지기도 한다

 

2. 방향을 바꾸고 DFS를 돌리면서 출력하기

다음과 같이 그래프의 방향이 주어졌을 때

 

원래 있던 그래프의 방향을 반대로 바꾸어준다

 

이제 DFS를 돌리면 된다

시작 노드를 3번 노드로 정하면

 

DFS에 따라 1번 노드나 4번 노드를 방문하게 된다

1번 노드나 4번 노드를 방문하고 해당 노드를 방문으로 표시하고 출력한다

위의 과정을 반복하면

나머지는 차례대로 4 2 3번 노드를 방문으로 표시하고 출력한다

나머지 방문하지 않은 노드를 다시 검사하여 남은 5번 노드를 출력하게 된다

어떤 노드를 시작점으로 설정했냐에 따라 출력이 달라질 수 있다

 

관련 문제: swea1267 작업순서

---