[알고리즘] DAG란?
[알고리즘] DAG란?
DAG(Directed Acyclic Graph)
- 직역하면, "방향성 비 사이클" 그래프(루프를 생성하지 않는 그래프)
- 루프(사이클) : 자기 자신에서 출발해서 다시 자기 자신에게 돌아오는 경로
- 3세대 블록체인이라고도 불림
- 순환 그래프가 아닌 비 순환 그래프
- 즉, 순환하는 싸이클이 존재하지 않고, 일방향성만 가짐
- 비가역적 일방향성적은 블록체인의 핵심적인 특성
순환 그래프란?
- 이런 그래프를 Negatvie Graph라고 함
- 그래프에서 볼 수 있듯이, A -> B -> C ->A의 싸이클이 발생하여 계속적으로 반복될 수 있는 상황이 발생
- 두가지 문제점이 생김
1. 오로지 긍정적인 위상(S, A, B, C, D)을 가져야 산출이 쉬워짐
2. A->B->C->A같은 순환이 없어져야 함
비 순환 그래프란?
- 계속적으로 순환 될 수 있는 구간이 없기 때문에, 순환그래프에서 발생하는 문제점들이 없음
- 이것을 위상정렬(Topologically sorted)라고 함
- DAG도 이런 비 순환 그래프
출처
댓글
댓글 쓰기