반응형 간선1 C++] 위상정렬 구현 및 설명 위상정렬은 각 노드들의 간선 개수를 구한 후 간선개수가 가장 적은 요소부터 순회하는 알고리즘입니다. 여기서 간선 개수란 각 노드마다 연결된 개수를 의미합니다. 간선 개수가 적은 요소들을 순회하기 때문에 한번에 원하는 지점까지 못가게 되는 특징이 있습니다. 위상정렬을 이용한 예제들은 주로 '게임 스킬트리, 우선순위에 대한 시간 문제 등...' 다양하게 사용되고 있습니다. 아래 그림을 통해 코드를 구현해 보겠습니다. 여기서 만약 A에서 E로 간다고 가정한다면 A는 B나 C를 거치고 D를 거처서 E로 가거나 혹은 D에서 F를 거처 E로 가게 됩니다. 즉, 노드 간선을 기점으로 모든 노드를 순서대로 거처가는걸 알 수 있습니다. 이 간선을 거처가는것이 하나의 조건이 될 수 있습니다. 아래는 구현 코드 입니다. #.. 2019. 9. 26. 이전 1 다음 728x90 반응형
