Topological Ordering, Topological Sort   위상 정렬

1. 방향성 비순환 그래프 (Directed Acyclic Graph, DAG)

  ㅇ 정점 간에(간선에) 방향은 있으나, 순환경로는 없는 그래프
     - 한 작업을 다른 작업 보다 우선 처리해야 하는, 순서 의존성을 모델링할 때 유용 함

  ㅇ (용어)
     - 진입 차수 (in-degree) : 한 정점으로 들어가는 간선의 개수
     - 진출 차수 (out-degree) : 한 정점에서 나오는 간선의 개수

  ㅇ 특징
     - 모든 DAG는, 진입 차수 및 진출 차수가 0인 정점을 각각 1 이상씩 포함
        . 그렇지 않으면, 순환이 존재하게 됨


2. 작업 순서 정렬 방법

  ㅇ 작업 사이에 특정한 의존 관계(선행 의무)가 있는 경우에 순서화시키는 정렬 방법을 찾음
     - 例) 선수 과목의 요구 등

  ㅇ 대표적인 例) 위상 정렬 알고리즘 (Topological Ordering)


3. 위상 정렬 알고리즘 (Topological Ordering)

  ㅇ 방향성 비순환 그래프에서, 정점들을 정렬하는 것
     - 결국, 1 이상의 선형적 순서를 생성해 냄 (정렬하는 방법이, 1 이상 가능)
        . 정점들의 순열을 구하는 문제

  ㅇ 특징
     - 만일, 그래프 내 순환이 있다면, 위상 정렬이 불가능 함

  ㅇ 알고리즘의 아이디어
     - ①  DAG에서, 진입 차수가 0인 정점을 선택 추가
     - ②  해당 정점과 그 간선을 모두 제거
     - ③  남겨진 DAG에서, 단계 ①을 반복

  ㅇ 알고리즘의 단계
     * (입력 : 방향성 비순환 그래프)
     - ① 새로운 빈 배열을 생성
        . 이때, 배열의 인덱스 : 정점 번호, 그 값 : 진입 차수
     - ② 배열 값(진입 차수)에 모두 0 대입
     - ③ 각 정점(배열의 각 요소)에 대해,
        . 이에 인접한 각 정점들의 진입 차수를 증가시킴
     - ... (편집중) ...