Algorithm/Study
2021. 9. 24.
그래프 이론 : 위상 정렬 알고리즘
위상 정렬 알고리즘 PRE. 진입차수 : 특정한 노드로 들어오는 간선의 개수 위상 정렬 알고리즘 개념 - 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' - 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용한다. - ex. 선수 과목을 고려한 학습 순서 설정 - 시간 복잡도 : O(V +E) // 차례대로 모든 노드 확인하고, 해당 노드에서 출발하는 간선을 차례대로 제거. (노드, 간선 둘다 확인) - 과정 1) 진입차수가 0인 노드를 큐에 넣는다. 2) 큐가 빌 때까지 다음의 과정을 반복한다. 2-1) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2-2) 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. (모든 원소를 방문하기 전에 큐..
