mininum spanning tree1 [알고리즘] 최소 신장 트리 MST (Minimum Spanning Tree) 개요 신장 트리 : 그래프의 모든 정점을 포함하는 트리최소 신장 트리 : 신장 트리들 중 가장 간선들 가중치의 합이 최소인 신장 트리입니다. 가장 큰 특징으로 트리 내 사이클이 존재하지 않습니다. 최소 신장 트리를 찾는 알고리즘 * Kruskal 각 간선의 가중치가 낮은 순으로 정렬가장 가중치가 낮은 간선 순으로 탐색해당 간선을 트리에 포함할 때 사이클이 없는 경우 -> 포함해당 간선을 트리에 포함할 때 사이클이 있는 경우 -> 제외 * Prim시작 정점에서 이동 가능한 간선 탐색가장 가중치가 낮은 간선 순으로 탐색해당 간선을 트리에 포함할 때 사이클이 없는 경우 -> 포함해당 간선을 트리에 포함할 때 사이클이 있는 경우 -> 제외 최소 신장 트리 판단을 위해 사용하는 자료구조, 알고리즘해당 트리가 최.. 2024. 9. 24. 이전 1 다음
