크루스칼 알고리즘(Kruskal's Algorithm)

크루스칼 알고리즘(Kruskal's Algorithm)

#include #include using namespace std; struct comp { bool operator()(vector a, vector b) { return a[2] < b[2]; } }; priority_queue, vector>, comp> pq; vector parents(1, 0); int get_parent(int i) { if (parents[i] != i) return get_parent(parents[i]); else return i; } int kruskal() { int answer = 0; while(pq.empty() == false) { int p0 = get_parent(pq.top()[0]), p1 = get_parent(pq.top()[1]); if ( p0 != p1 ) //이 간선의 두 노드가 서로 다른 트리에 속한다면 부모도 당연히 서로 다르다. { answer += pq.top()[2]; parents[max(p0, p1)] = min(p0, p1); //노드번호가 작은 쪽이 더 부모가 되도록 //노드번호가 큰 쪽의 parents[] 값을 갱신한다. (union) } pq.pop(); } return answer; } int main() { int V, E; cin >> V >> E; for (int i=1; i<=V; i++) parents.push_back(i); for (int i=0; i> n1 >> n2 >> w; pq.push({n1, n2, w}); } cout << kruskal(); return 0; }

공유하기 글 요소 저작자표시

from http://lkwks.tistory.com/24 by ccl(A) rewrite - 2021-09-25 02:00:56