신장트리1 [WEEK03] 신장트리와 최소신장트리 (크루스칼 + 프림 알고리즘) 1. 신장트리 Spanning Tree - 신장트리는 그래프 알고리즘 문제로 자주 출제되는 문제유형 - 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 - 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 함 최소신장트리 알고리즘 (MST; Minimum Spanning Tree) - 신장트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘 2. 크루스칼 알고리즘 특징 - 대표적인 최소신장트리 알고리즘 중의 하나 - 그리디 알고리즘으로 분류 - 모든 간선에 대해 정렬을 수행한 뒤에 가장 짧은 간선부터 집합에 포함시킴 (이때 사이클을 발생시킬 수 있는 간선의 경우 집합에 포함시키지 않음 => 최적의 해 보장) .. 2022. 10. 10. 이전 1 다음
