최근 수정 시각 : 2023-07-31 00:40:55

위상 정렬


'''이론 컴퓨터 과학
{{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"'''
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin: -5px -1px -11px"		<colbgcolor=#aa3366> 이론
기본 대상 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학
다루는 대상과 주요 토픽
계산 가능성 이론 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버
오토마타 이론 FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임
계산 복잡도 이론 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법)
정보이론 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학
프로그래밍 언어이론 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론
주요 알고리즘 및 자료구조
기초 정렬 알고리즘 · 순서도 · 탐색 알고리즘
추상적 자료형 및 구현 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^
수학적 최적화 조합 최적화 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습
볼록 최적화 내부점 방법 · 경사하강법
선형계획법 심플렉스법
계산 수론 및 암호학 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호
대칭키 암호화 방식 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4)
공개키 암호화 방식 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9)
계산기하학 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN
그래프 이론 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론
정리
정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결
틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 }}}}}}}}}


파일:Q3MA6dZ.png
1. 개요2. 정의
2.1. 조건2.2. 비전공자를 위한 설명
3. 알고리즘
3.1. Kahn 알고리즘
3.1.1. 의사 코드
3.2. DFS
4. 활용5. 관련 문서

[clearfix]

1. 개요

Topological Sort / Topological Ordering

순환하지 않는 유향 그래프를 방향성에 거스르지 않도록 순서대로 배열하는 방법.

2. 정의

부분 순서 집합 [math(\left(A,\preceq\right))]에 대해, 이를 [math(\forall a,b\in A(a\preceq b\to a\preceq_T b))] 를 만족하는 전순서 관계 [math(\left(A,\preceq_T\right))] 를 생각할 수 있으며 이와 같이 어떤 부분 순서 관계와 호환되는(compatible)[1] 전순서 관계를 만드는 과정을 [math(A)]의 위상 정렬이라고 한다.

모든 유한 부분 순서 집합은 유향 그래프 [math(G=(V,E))]로 나타낼 수 있으므로, 해당 그래프에서 모든 [math(e\in E)] 인 모든 [math(e=(u,v))]에 대해 [math(u)]가 [math(v)]보다 앞에 위치하도록 만드는 과정을 유향 그래프 [math(G)]의 위상 정렬이라고 한다.

2.1. 조건

위상 정렬이 가능하려면 해당 그래프는 방향이 있고 순환하지 않는 그래프(Directed Acyclic Graph)여야 한다. (흔히 줄여서 DAG로 부른다)

무향 그래프라면 정렬이 의미가 없고 순환하는 그래프라면 위상 정렬이 불가능하다. 이는 사이클을 부분 그래프로 가지는 경우 후술한 진입차수가 절대 0이 되지 않는 구간이 발생하기 때문.

2.2. 비전공자를 위한 설명

간단한 비유로, 지금부터 라면을 준비한다고 생각해보자. 라면을 요리하는 단계는 '사리 부수기', '스프 넣기', '끓이기', '밥 준비하기', '사리 넣기', '물 넣기', 등 여러 가지 작업으로 나눌 수 있을 것이다. 순서가 뭔가 이상하다고 느꼈다면 정상이다. 우선 필수적인 순서부터 정리해보자. 물을 넣기 전에 스프나 사리부터 넣을 수는 없다. 물을 넣기 전에 끓이는 것 역시 불가능하다. 사리를 넣고 나서는 부술 수 없다.[2] 하지만 스프를 먼저 넣냐 사리를 먼저 넣냐는 큰 상관이 없다. 끓이기 역시 마찬가지다. 밥 준비하기는 라면 준비와는 아예 별도의 독립적인 과정이다.

파일:toposort-example.svg

이러한 부분적인 순서 관계만 있는 상황에서, 요리를 하는 사람은 자신이 원하는 대로 전체 레시피를 완성할 수 있다. 예를 들어 물 넣기 → 스프 넣기 → 끓이기 → 사리 부수기 → 사리 넣기 → 밥 준비하기 도 가능하며 사리 부수기 → 물 넣기 → 사리 넣기 → 밥 준비하기 → 스프 넣기 → 끓이기 도 멀티태스킹이 된다면 가능하다. 하지만 끓이기 → 스프 넣기 → 사리 넣기 → 밥 준비하기 → 물 넣기 → 사리 부수기 와 같은 레시피는 올바른 라면을 만들 수 없다. 앞서 정의한 순서를 위반하기 때문이다. 이와 같이 주어진 순서 조건들을 만족시키도록 정렬하는 행위를 '위상 정렬'이라고 이해하면 좋다.

3. 알고리즘

크게 Kahn 알고리즘과 DFS로 나눌 수 있으며, 두 알고리즘 모두 [math(\mathcal{O}(V+E))]의 시간복잡도를 지닌다.

이 두 알고리즘을 이해하려면 진입차수와 진출차수에 대해 알아야 한다.
두 알고리즘 모두 진입차수가 0인 노드를 엣지와 함께 순서대로 제거하는 방식으로 이루어진다.

이 때, 순환하지 않는 유향 그래프가 진입차수가 0인 노드를 반드시 하나 이상 포함한다는 사실은 증명되어 있기 때문에 시작점으로 사용할 노드 S를 고른다.

3.1. Kahn 알고리즘

  1. 진입차수가 0인 노드를 전부 큐 Q에 집어넣는다.
  2. 큐에서 노드 하나를 뽑아 해당 노드가 가리키는 모든 노드의 진입차수를 1씩 줄인다.
  3. 큐가 빌 때까지 2를 반복한다.
  4. 그래프가 완전히 비지 않았다면 1로 돌아간다.

이때 최종적으로 Q에서 빠져나간 순서가 위상 정렬된 순서가 된다.

3.1.1. 의사 코드

Q가 빌 때까지 반복:
    Q에서 v를 뽑는다.
    v를 L에 추가한다.
    v에서 출발하는 모든 간선 e에 대해:
        e의 도착지 u의 진입차수를 1 내린다.
        만약 u의 진입차수가 0이라면:
            u를 Q에 추가한다.

3.2. DFS

  1. 임의의 노드 S를 고른다.
  2. DFS로 그래프를 탐색하며 진출차수가 0인 노드에서 멈춘다.
  3. 해당 노드를 스택에 넣는다.
  4. 2로 돌아가 다시 거슬러 올라가 탐색한다.
  5. 만약 더이상 갈 수 있는 곳이 없다면 다시 임의의 노드 S2를 골라 2로 돌아간다.
  6. 그래프가 빌 때까지 반복한다.

이때 노드를 스택에서 뺀 순서가 위상 정렬된 순서가 된다.

4. 활용

  • 작업 스케줄링, 종속성 처리
    여러 작업들이 서로 먼저 처리해야 하는 종속성을 가지고 있는 경우 가장 활용하기 좋다. Make와 같은 빌드 시스템, npm등의 패키지 매니저, 운영체제의 프로세스 스케줄링까지 다양한 분야에서 활용된다.
    • 데이터 직렬화
      만약 직렬화 하려는 한 객체가 다른 객체에 대한 참조를 가지고 있다면, 시리얼라이저는 이 종속성 관계를 파악해 가장 안쪽 객체부터 차례대로 처리한다.[3]
  • 부분 정렬
    만약 주어진 데이터가 항상 서로 비교 가능하다면 정렬 알고리즘을 사용할 수 있지만, 데이터에 비교된 값의 일부만 포함된 경우 또는 소실된 경우, 위상 정렬을 사용해 주어진 조건을 만족하는 정렬된 상태를 찾을 수 있다.
  • 심볼 추적
    컴파일러가 소스 코드를 파싱하고 심볼 테이블을 작성할 때, 한 심볼이 다른 심볼에 대한 참조를 가질 수 있다(class 등의 경우.) 이 때 심볼 테이블을 그래프로 만들고 위상 정렬을 통해 테이블 순서를 재정렬하는 과정을 거친다.
  • 사이클 감지
    사이클이 존재하는 그래프는 위상 정렬이 반드시 실패한다는 점을 역으로 이용해 주어진 그래프가 순환하는지 여부를 검증하는 데에도 사용할 수 있다. 흔히 데드락 등 교착 상태에서의 사이클을 감지하고 해결하기 위해 사용된다.

5. 관련 문서

[1] 즉 [math(\preceq)]는 [math(\preceq_T)]의 부분 집합이라고 할 수 있으며 이를 만족하는 [math(\preceq_T)]는 경우에 따라 무수히 많이 존재할 수 있다. 따라서 위상 정렬은 일반적으로 주어진 입력에 대해 조건을 만족하는 여려 결과가 나올 수 있다.[2] 사리를 부수냐 그대로 넣냐는 취향에 따라 갈리지만 본 예시에서는 복잡한 그래프를 만들기 위해 부수는 단계를 필수로 가정한다.[3] When serializing data objects that have dependencies on each other, topological sorting can be used to ensure that each object is serialized after its dependencies.

분류