Union-Find2 최소신장트리(Minimal Spanning Tree)_크루스칼(Kruscal) 알고리즘 최소신장트리(MST)에 대한 이해 - 신장트리란, 뱡향성이 없는 그래프의 부분그래프(Subgraph)들 중에서, 모든 정점을 포함하는 트리이다. - 최소신장트리란, 신장트리들 중에서 간선의 합이 가장 작은 트리를 말한다. - 그래프에서 최소신장트리는 여러 개 있을 수 있다. 최소신장트리를 구하는 알고리즘으로는 크게 크루스칼(Kruscal) 알고리즘과 프림(Prim) 알고리즘이 있으며, 해당 글에서는 크루스칼 알고리즘의 방법을 다룬다. V(노드의 개수) = 6, E(간선의 개수) = 7 인 다음과 같은 그래프에서 최소신장트리의 간선 길이의 합을 구해보자. 간선들 중, 가장 길이가 짧은 간선을 선택하여 연결된 두 노드를 확인한다. 만약 두 노드가 다른 집합에 속해있다면 두 노드를 같은 집합에 포함시키고 해당.. 2022. 3. 4. 유니온파인드(Union-Find) Union-Find 에 대한 이해 - 공통 원소가 없는, "상호 배타적"인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. - 원소들이 어떠한 집합에 포함되어있을 때, 특정 원소가 포함되어있는 집합을 찾는 Find 연산을 지원한다. - 두 원소들이 속한 집합이 다를 때, 두 집합을 하나의 집합으로 합치는 Union 연산을 지원한다. 트리 형태로 표현되어있는 원소들간의 서로소 집합을 살펴보자. 위의 그림에서 원소들의 상호 배타적 집합은 총 4개이다. 각 원소들은 하나의 집합에 포함되어있고, 같은 집합에 포함되어있는 원소들은 같은 루트 노드를 공유한다. 예를 들어, 노드 2번과 노드 4번은 같은 집합에 포함되어 하나의 트리로 연결되어있고 루트 노드 1번을 공유한다. 노드 6번과 노.. 2022. 3. 3. 이전 1 다음