MST
Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소가 되는 트리
네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것
Spanning Tree
그래프 내의 모든 정점을 포함하는 트리
n개의 정점을 n - 1개의 간선으로 연결
임의의 정점 선택 후 linked_node_list
에 append
1에서 선택한 정점과 연결된 간선들을 edge_list
에 append
edge_list
에서 최소 가중치를 가지는 간선부터 pop
linked_node_list
에 들어있다면 continue
linked_node_list
에 들어있지 않다면 해당 간선을 선택 후 간선 정보를 MST
에 append
edge_list
에 간선이 없을 때까지 3번을 반복
Disjoint Set을 표현할 때 사용하는 트리 구조를 활용한 알고리즘
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
Union
두 개의 트리를 하나의 트리로 합친다
만약 두 트리의 높이가 다르면 높이가 큰 트리에 높이가 작은 트리를 붙인다
두 트리의 높이가 같다면 한 쪽의 트리 높이를 증가시켜준 뒤 트리를 합친다
Find
여러 노드가 존재할 때, 두 개의 노드를 선택 후 각 노드의 루트 노드를 확인하여 서로 같은 그래프에 속하는지 판별
path compression
Find를 실행한 노드를 루트 노드에 다이렉트로 연결하는 기법
제가 찾던 최소신장트리 여기있네요