MST (2) 썸네일형 리스트형 머지 소트 트리 Merge Sort Tree 머지 소트 트리는 세그먼트 트리의 파생형으로 위 그림처럼 각 node가 정렬된 구간을 보유하는 형태로 되어있다. 머지 소트 트리는 세그먼트 트리와 유사하게 구현할 수 있다. 초기화 void set_mst(int node, int start, int end) { vector &cur = mst[node]; if (start == end) { cur.push_back(ar[start]); return; } int m = mid(start, end); set_mst(node * 2, start, m); set_mst(node * 2 + 1, m + 1, end); vector &l = mst[node * 2], &r = mst[node * 2 + 1]; cur.resize(l.size() + r.size()).. MST 최소 신장 트리 Sollin, Boruvka (솔린, 보르부카) 알고리즘 구현 이 게시글에서는 솔린, 해외에서는 보르부카라는 이름으로 더 알려져 있는 MST 생성 알고리즘을 구현해보겠다. 솔린 알고리즘의 간단한 설명 주어진 그래프에서 각 노드들을 트리라 생각한다. 그러면 그래프는 포레스트가 된다. 각 트리에서 다른 트리로 연결된 최소 비용 엣지를 택하여 그 엣지로 연결된 두 트리를 union하는 것을 포레스트가 하나의 트리가 될 때까지 반복하면 MST가 완성된다. 단계마다 모든 엣지들을 탐색하면서 포레스트에 들어있는 트리의 개수가 절반씩 줄어들다가(한 트리는 다른 트리와 무조건 짝지어지게 됨을 생각하면 이해할 수 있다.) 1개, 즉 MST가 되면 종료하므로 시간 복잡도는 $O(ElogV)$이다. 구현 - 백준 1197번 풀기 union하는 것에서 눈치챌 수 있듯이 솔린 알고리즘도 .. 이전 1 다음