728x90
반응형
알고리즘 - 위상정렬 (Topological Sort)
DAG(비순환 방향 그래프)에서 그래프의 방향성을 거스르지 않고 정점들을 나열하는 알고리즘으로 위상정렬은 각 정점을 우선순위에 따라 배치한다. 일반적으로 결과는 유일하지 않다.
jina-developer.tistory.com/112
자료구조 - DAG (Directed Acyclic Graph)
1. Directed Acyclic Graph란? DAG란 순환을 가지지 않는 방향그래프를 말한다. 일반적으로 우선순위를 가진 일련의 작업들은 DAG구조를 가진다. - 선행자(predecessor), 후행자(successor) : DAG에서 어떤 정점 v..
jina-developer.tistory.com
- 각 노드들의 진입 차수 계산
- 진입 차수가 0인 노드들을 큐에 삽입
- 큐에서 노드를 꺼내 연결된 간선을 제거
- 제거로 인해 진입 차수가 0이 된 노드를 큐에 삽입
- (3)~(4) 번을 반복하며 큐가 비었으면 종료
728x90
반응형
'BASE > Alogorithm' 카테고리의 다른 글
| 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) (0) | 2021.02.03 |
|---|---|
| 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) (0) | 2021.02.02 |
| 알고리즘 - 에라토스네스의 체 (0) | 2021.02.02 |
| 알고리즘 - 유클리드 호제법 (0) | 2021.02.02 |
| 알고리즘 - 너비 우선 탐색 (Breadth First Search) (0) | 2021.01.27 |
댓글