최소 신장 트리 (Minimum Spanning Tree) 주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 선분들의 가중치 합이 최소인 트리 (b)는 최소 신장 트리 (c)는 가중치의 합이 (b)보다 큼 (d)는 트리가 주어진 그래프의 모든 노드를 포함하지 않음 Idea 사이클이 없도록 모든 점을 연결 그래프의 점의 수가 n인 경우 신장 트리에 (n - 1)개의 선분이 존재 트리에 선분을 하나 추가할 경우, 반드시 사이클이 형성 관련 알고리즘 크러스컬 (Kruskal) 알고리즘 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 2024.03.10 - [Algorithm] - [알고리즘] 크러스컬 최소 신장 트리 (Kruskal MST) 프림 (Prim) 알..
