[알고리즘] 위상 정렬(Topology Sort)

hugingstar·2022년 4월 8일
0
post-thumbnail

오늘은 위상 정렬을 정리해보자..

위상 정렬

순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘

특징

  1. 여러개의 답이 있을 수 있다.
  2. DAG(Directed Acyclic Graph)에만 적용 가능 : 방향은 있는데, 사이클이 없는 경우에만 위상 정렬이 가능하다. (사이클이 발생하면 시작점을 규정하기가 어렵기 때문에)

해결 방식

  1. Stack 방식
  2. Queue 방식

예시

아래 그림을 보면 각 노드들이 있다. 이 노드들은 어떤 처리 과정을 나타내고, 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.순서가 모두 결정되었다.

0개의 댓글