-
[알고리즘] #12. 위상정렬(Topological Sort)Algorithm/알고리즘 2020. 2. 18. 13:14
#위상정렬
어떠한 일을 하기 위한 순서를 탐색하는 알고리즘
즉, "순서가 정해져있는 작업"을 수행할때 그 순서를 결정하기위한 알고리즘
방향 그래프에 존재하는 각 정점의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는것 => 그래프를 정렬
##조건
DAG(Directed Acyclic Graph): 방향성이 있고, 사이클이 없는 그래프
##특징
하나의 그래프에는 여러개의 위상정렬이 존재한다.
##알고리즘
1. 진입차수가 0인 정점을 큐에 삽입.
2. 큐에서 원소를 꺼내고, 모든 간선을 제거
3. 간선을 제거한 이후에 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌때까지 2~3번 과정을 반복
모든원소를 방문: 위상정렬의 결과는 큐에서 꺼낸 순서
모든원소를 방문하기전에 큐가 비는경우: 사이클이 존재하는 그래프
'Algorithm > 알고리즘' 카테고리의 다른 글
[알고리즘] #13. SCC(코사라주, 타잔) 알고리즘 (0) 2020.02.26 [알고리즘] #11. DP(DynamicPrograming): 비트마스킹(외판원 순회) (0) 2020.02.16