5.TIL - 신장트리, MST, 크루스칼, union-find
신장트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리(필연적으로 연결 트리이다.) 최소 연결 = 간선의 수가 가장 적다. N개의 정점에서는 간선이 N-1개가 된다. 사용 : N개의 정점을 최소의 케이블을 사용하여 연결하고자 하는 경우(통신 네트워크) MST 최소신장트리(Minimun Spanning Tree) 신장트리에서 간선의 가중치 합이 최소인 트리 나올 수 있는 여러 개의 신장트리중에 간선의 가중치의 합이 가장 작은 트리 사이클이 포함되지 않는다!(신장트리 자체가 최소 간선이므로 사이클이 있을 필요가 없다.) MST 구현 방법 - 크루스칼 알고리즘 간선을 선택하는 알고리즘 간선을 정렬한 뒤 작은 순서대로 선택(Greedy) 이 때, 사이클을 형성하는지 체크한다. 추가하고자 하는..
공부/T.I.L(2021)
2021. 1. 14. 16:00