spanning tree1 [코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9. 이전 1 다음 반응형
