위상정렬

위상정렬 이란

올바른 위상정렬
- ABCDEF
- ACEDBF
- BADCEF
- BADFCE

올바르지 않은 위상정렬
- BFACED는 F가 D보다 먼저 나오기 때문에 잘못된 위상정렬이다.

자신보다 앞에 위치하는 정점이 없어야한다.
자신에게 들어오는 간선이 없어야한다.
indegree - 자신에게 들어오는 간선의 수

위상정렬 알고리즘

1.맨 처음 모든 간선을 읽으며 indegree 테이블을 채움
2.indegree가 0인 정점들을 모두 큐에 넣음
3.큐에서 정점을 꺼내어 위상 정렬 결과에 추가
4.해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킴 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가
5.큐가 빌 때 까지 3,4번 과정을 반복

위상정렬은 사이클이 존재하면 모순이 발생

A, B, C 중 어느것이 먼저 나오더라도(순서와 상관없이)
간선으로 주어진 정점 간 선후관계에 모순이 발생한다.
위상정렬은 사이클이 존재하지 않는 방향 그래프에서만 잘 정의된다.
DAG(Directed Acyclic Fraph) - 사이클이 존재하지 않는 방향그래프