문제4) 방향성 비순환 그래프(Directed Acyclic Graph)에 대하여 다음 물음에 답하시오.
가. 방향성 비순환 그래프의 개념과 특징
나. 아래 방향성 비순환 그래프에 대하여 위상정렬(Topology Sort)을 실시하고 결과값 제시
답)
1. 방향성 비순환 그래프(DAG; Directed Acyclic Graph) 개념
가. 방향성 비순환 그래프 정의
- 개별 요소들이 특정한 방향을 향하고 있으며, 서로 순환하지 않는 구조로 짜여진 그래프
나. 방향성 비순환 그래프 특징
- 유향 비순환 그래프
- 여러 개의 트랜잭션을 하나의 블록으로 묶지 않고, 각 개별 요소들끼리 상호 연결
- 몬테 카를로(MCMC; Markov Chain Monte Carlo) 알고리즘 사용
2. 위상정렬의 개념과 결과 값
가. 위상정렬의 정의
- 유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열한 정렬 알고리즘
- 깊이 우선 탐색(Depth First Search, DFS)로 풀 수 있는 대표적인 정렬 방법
나. 위상정렬 실시 결과 값 제시
 |
|
공감과 댓글은 아이티신비에게 큰 힘이 됩니다.
블로그 글이 유용하다면 블로그를 구독해주세요.♥