오늘은 위상 정렬을 정리해보자..
순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
아래 그림을 보면 각 노드들이 있다. 이 노드들은 어떤 처리 과정을 나타내고, 7 번까지 업무가 진행되려면, 순서를 따라서 업무가 단계별로 진행되어야 한다. 그리고 6 번 과정이 진행되려면 선결로 4, 5번 과정이 완료가되어야 한다.(4, 5가 진입차수를 만들어 낸다.즉, 6의 진입차수는 2이다.)
방법은 아래와 같은데,
1. 집입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복한다.
모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고,
모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.
진입차수를 그림과 표로 나타내면 깔끔하게 정리가 가능하다.
1.진입차수가 0인 정점 1을 큐에 삽입한다.
2.정점 1을 큐에서 빼내고 간선을 모두 제거해준다.
3.진입차수가 0인 새로운 정점들을 다시 큐에 삽입해준다.
4.큐에서 정점 2를 빼고 간선을 모두 제거해준다.
5.여기서 잠깐, 정점 3번이 진입차수가 0인 것이 확인되었다. 정점 3을 큐에 넣는다.
6.큐에서 정점 5를 빼고 간선을 모두 제거해준다.
7.진입차수가 0인 새로운 정점은 발견되지 않았다. 정점 6번을 보면, 2-1=1해서 1개 차수가 남아서 진입차수 0이 아니다.
8.큐에서 정점 3을 빼고 간선을 모두 제거해준다.
9.진입차수가 0인 새로운 정점 4가 발견되었다. 큐에 추가한다.
10.정점 4를 큐에서 빼고 간선을 모두 제거해준다.
11.진입차수가 0인 새로운 정점 6이 발견되었다. 큐에 추가한다.
12.정점 6을 큐에서 빼고 간선을 모두 제거해준다.
13.진입차수가 0인 새로운 정점 7이 발견되었다. 큐에 추가한다.
14.정점 7을 큐에서 빼고 간선을 모두 제거해준다.
15.순서가 모두 결정되었다.