위상정렬 (Topological sort)

개념

DAG에서 의존성에 맞게 그래프의 정점을 정렬

DAG (Directed Acyclic graph)

간선에 방향이 존재하고,  사이클(cycle)이 없는 그래프.

DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는데 많이 사용

 

※의존성 그래프(dependency graph)

작업(정점)간의 의존 관계를 간선으로 표현한 방향 그래프

 

DAG에서 간선의 방향이 모두 한 방향으로 흘러가게 정점들을 정렬됩니다.

간선의 방향이 모두 한 방향으로 흐르며, 

방향성을 거스르는 간선이 없게 정렬을 하기 위해서는 사이클이 없어야 합니다.

* 작업의 순서(의존관계)만 위반하지 않으면 되므로 여러 순서(결과)가 나옵니다.

(i) → (f) → (b) →  (e) → (d) → (c) → (a) → (h) → (g)

(i) → (b) → (e) →  (f) → (d) → (c) → (a) → (h) → (g)

(i) → (d) → (c) →  (a) → (f) → (b) → (e) → (h) → (g)

...

(i)가 (d), (b), (f) 보다 앞서야 하며,

(d), (b), (f)간에는 순서가 상관 X

이는 다른 정점에서도 마찬가지입니다.

 

구현

① 그래프 표현(인접리스트, 인접행렬)

② 위상정렬 구현 (진입차수indegree, DFS)

    - 사이클 형성 유무 확인

    - 위상정렬 결과 중 다른 제약이 있는지.    

        ex) 여러 위상정렬 결과를 인정하는지 등

 

관련 문제

- [BOJ] 10451 순열 사이클 (단순 사이클 우뮤 확인)

- [BOJ] 9466 텀 프로젝트 (단순 사이클 우뮤 확인)

- [BOJ] 2252 줄 세우기 (사이클 유무 확인 X) 

★ [BOJ] 2623 음악 프로그램  (인접리스트 + 사이클 유무 확인)

★ [BOJ] 1516 게임개발 (진입 차수 이용한 위상정렬)

★ [BOJ] 1005 ACM Craft

★ [BOJ] 2056 작업

- [BOJ] 1766 문제집

★ [BOJ] 3665 최종 순위

- [BOJ] 2848 알고스팟어

- [SWEA] 3952 줄 세우기

- [SWEA] 1267 작업순서

- [Algospot] DICTIONARY 고대어 사전