1. 방향성 비순환 그래프 (Directed Acyclic Graph, DAG)
ㅇ 정점 간에(간선에) 방향은 있으나, 순환경로는 없는 그래프
- 한 작업을 다른 작업 보다 우선 처리해야 하는, 순서 의존성을 모델링할 때 유용 함
ㅇ (용어)
- 진입 차수 (in-degree) : 한 정점으로 들어가는 간선의 개수
- 진출 차수 (out-degree) : 한 정점에서 나오는 간선의 개수
ㅇ 특징
- 모든 DAG는, 진입 차수 및 진출 차수가 0인 정점을 각각 1 이상씩 포함
. 그렇지 않으면, 순환이 존재하게 됨
2. 작업 순서 정렬 방법
ㅇ 작업 사이에 특정한 의존 관계(선행 의무)가 있는 경우에 순서화시키는 정렬 방법을 찾음
- 例) 선수 과목의 요구 등
ㅇ 대표적인 例) 위상 정렬 알고리즘 (Topological Ordering)
3. 위상 정렬 알고리즘 (Topological Ordering)
ㅇ 방향성 비순환 그래프에서, 정점들을 정렬하는 것
- 결국, 1 이상의 선형적 순서를 생성해 냄 (정렬하는 방법이, 1 이상 가능)
. 정점들의 순열을 구하는 문제
ㅇ 특징
- 만일, 그래프 내 순환이 있다면, 위상 정렬이 불가능 함
ㅇ 알고리즘의 아이디어
- ① DAG에서, 진입 차수가 0인 정점을 선택 추가
- ② 해당 정점과 그 간선을 모두 제거
- ③ 남겨진 DAG에서, 단계 ①을 반복
ㅇ 알고리즘의 단계
* (입력 : 방향성 비순환 그래프)
- ① 새로운 빈 배열을 생성
. 이때, 배열의 인덱스 : 정점 번호, 그 값 : 진입 차수
- ② 배열 값(진입 차수)에 모두 0 대입
- ③ 각 정점(배열의 각 요소)에 대해,
. 이에 인접한 각 정점들의 진입 차수를 증가시킴
- ... (편집중) ...