MST1 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘 최소신장트리(MST)에 대한 이해 - 신장트리란, 뱡향성이 없는 그래프의 부분그래프(Subgraph)들 중에서, 모든 정점을 포함하는 트리이다. - 최소신장트리란, 신장트리들 중에서 간선의 합이 가장 작은 트리를 말한다. - 그래프에서 최소신장트리는 여러 개 있을 수 있다. 최소신장트리를 구하는 알고리즘으로는 크게 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있으며, 해당 글에서는 크루스칼 알고리즘의 방법을 다룬다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 최소신장트리의 간선 길이의 합을 구해보자. 간선들 중, 가장 길이가 짧은 간선을 선택하여 연결된 두 노드를 확인한다. 만약 두 노드가 다른 집합에 속해있다면 두 노드를 같은 집합에 포함시키고 해당.. 2022. 3. 4. 이전 1 다음