현인

MST(Minimum Spanning Tree) - 최소 신장 트리 Spanning Tree(신장 트리)란? 그래프 내의 모든 정점을 포함하는 트리 단, 최소 연결 그래프 형태이다. n개의 정점을 가지는 그래프에서 n-1개의 간선으로 연결된 트리이다. 하나의 그래프에는 여러 개의 신장트리가 존재한다. Minimum Spanning Tree(최소 신장 트리)란? 신장 트리 중에서 사용된 간선들의 가중치 합이 가장 작은 신장 트리 MST 구현 방법 크루스칼(Kruskal) 프림(Prim) 크루스칼 (Kruskal) 간선을 기준으로 접근한 방법 모든 간선을 가중치가 낮은 간선을 우선으로 정렬한 후에 가중치가 가장 낮은 간선부터 하나 씩 MST 집합에 추가를 한다 이 때, 사이클을 형성하는지 검사를 한다 사이클..