위상정렬

위상정렬이란

위상정렬은 DAG 이라고도 불리는 알고리즘입니다. 이 알고리즘은 어떤 일을 하는 순서를 찾는 알고리즘입니다.

방법

1. 진입 차수가 0인 정점을 시작 정점으로 정합니다.
2. 시작 정점과 연결되어 있는 모든 간선을 제거합니다.
3. 간선을 제거해줘 진입차수가 0이 된 정점을 제거해줍니다
4. 위 과정을 반복합니다.

같이 떡볶이를 만들면서 위상 정렬을 해봅시다!

이렇게 저는 떡볶이를 만드는 순서를 간단히 정리했습니다.

진입 차수가 0인 재료 준비라는 정점을 시작 정점으로 잡았습니다. 이 정점을 큐에 넣어줍니다.

재료준비를 큐에서 빼준 다음 연결되 있던 모든 간선을 제거해줍니다.

진입차수가 0인 양념장 만들기와 물 끓기를 큐에 넣어줍니다! 이때 순서는 상관 없습니다. 저는 일단 양념장 만들기를 먼저 넣어주겠습니다.

양념장 만들기는 빼준 다음 연결된 간선을 다 제거해줍니다.

이러한 방법으로 진행해줍니다!

특징

1. 싸이클이 있으면 위상 정렬을 사용하지 못한다.
   - 싸이클이 존재한다면 진입 차수가 0인 정점을 기준으로 정렬을 시작하는데 싸이클이 있다면 시작 정점을 찾을 수 없습니다. 밑에 그래프처럼요!
   

2. 하나의 방향 그래프로 여러 유형의 위상 정렬이 가능하다.

3. 정렬 중 진입 차수가 0인 정점이 없다면 정렬을 중단합니다.

블록체인 적용

DAG 알고리즘은 블록체인 쪽에서 미래가 밝은 알고리즘입니다!

1. 사용자가 많을 수록 빠르다.
   • DAG 알고리즘을 적용하면 블록이 없기 때문에 승인을 기다릴 필요가 없어집니다. 또한 검증 과정이 병렬적으로 이루어져 속도가 더욱 빨라진다고 합니다.
2. 수수료가 없다.
   • 블록의 개념이 사라져 DAG 방식에서는 수수료가 발생하지 않습니다.
3. 확장성 문제가 없다.
   • 사용량이 많아질수록 검증할 것이 많아져 검증의 신뢰도와 속도가 증가합니다.