반응형
위상 정렬
순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘, 또는 방향 그래프의 모든 노드를 방향성에 어긋나지 않고 순서대로 나열하는 것으로 정의할 수 있다.
위상 정렬을 2단계로 설명할 수 있는데 다음과 같다.
- 진입차수가 0인 노드를 큐에 넣는다.
- 큐가 빌 때까지 다음의 과정을 반복한다.
- 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.
- 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.
이때 진입차수란?
이는 한 노드로 방향을 가르키는 간선의 개수를 의미한다.
파이썬 소스
반응형
'Algorithm > algorithm' 카테고리의 다른 글
소수 구하기 - 에라토스테네스의 체 (Python & JavaScript) (0) | 2022.05.02 |
---|---|
그래프 - 깊이우선탐색 / 너비우선탐색 ( DFS / BFS ) (0) | 2021.10.18 |
신장 트리 (Spanning Tree) & 크루스칼(Kruskal) (0) | 2021.09.13 |
동적 계획법(Dynamic Programming, DP) (0) | 2021.09.01 |