일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 창훈쓰다
- 외판원 순회
- 삼성 코딩테스트
- 안드로이드 스튜디오
- 그리디 알고리즘
- 비트마스크
- 언어의 온도
- 백트레킹
- 캘리그라피
- yolo
- BFS
- 다음 지도 api
- MST
- Segment Tree
- 성화봉송
- 위상정렬
- 영어회화 100일의 기적
- BOJ 2098
- multiset
- 평창동계올림픽
- 생활코딩
- boj
- DP
- 인간이 그리는 무늬
- 다이나믹 프로그래밍
- 다음 API
- lower_bound
- upper_bound
- 성화봉송주자
- 이분탐색
- Today
- Total
Hoon222y
MST - 프림(Prim), 크루스칼(Kruskal) 알고리즘 본문
MST 는 Minimum Spanning tree 인데 용어를 간략히 정리하자면
스패닝 트리 : 그래프에서 일부 간선을 선택해 만든 트리
최소 스패닝 트리: 스패닝 트리 중에 선택한 간선의 가중치의 합이 최소인 트리 (트리의 정의 : 정점이 N개라면 간선은 N-1개인 경우 )
MST를 구현하는 방법에는 크게 3가지로 나누어 볼 수 있는데
1) 프림 (Prim) - 정점을 중심으로
2) 크루스칼 (Kruskal) - 간선을 중심으로
3) 솔린 알고리즘 (sollin's algorithm)
으로 나누어 볼 수 있다. 근데 보통은 같은 시작 복잡도를 가지고 있으므로 간단한 크루스칼을 많이 사용하는것 같다. 해당 포스팅에서는 크루스칼까지만 언급을 하도록 하겠다.
먼저 프림(Prim algorithm)의 경우
1. 그래프에서 임의의 한 지점을 선택한다.
2. 선택한 정점과 선택하지 않은 정점을 연결하는 간선중에 최소값을 구한다. (u,v라고 표현한다면 u는 선택한 정점 , v는 선택하지 않은 정점)
3. 선택한 간선을 MST에 추가하고, v를 선택한다.
4. 모든 정점을 선택하지 않았다면 2번으로 돌아가서 반복한다.
해당과 같은 그림이 있다면 임의의 한 정점을 선택하고 그 점을 기점으로 시작하는 것이다. (그림에서는 1을 선택한 모습)
그렇다면 프림의 시간복잡도는 어떻게 될까??
각각의 정점에 대하여 모든 간선들을 살펴 본게 되므로 시간복잡도는 O(V*E) 이며 최대 O(N^3)이라고 한다 .
구현의 경우에는 2번 과정에서 '연결하는 간선중에 최소값을 구한다' 라고 적혀있기 때문에 매번 최소값을 찾을때 효율적인 .. Priority_queue를 사용한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | for(int i=0;i<line;i++){ int a,b,c; scanf("%d %d %d" , &a, &b, &c); arr[a].push_back(make_pair(b,c)); arr[b].push_back(make_pair(a,c)); } check[1] = true; priority_queue<pair<int,int>> q; for (auto &p : arr[1]) { //arr[1]에 있는 모든 pair형을 다 반복한다. q.push(make_pair(-p.second,p.first)); } int answer =0; while(q.empty() != 1){ auto p = q.top(); //auto로 인하여 p가 자동적으로 Pair형이 된다. q.pop(); if(check[p.second] == true){ //끝점이 방문된적이 있다면 그 경우는 스킵한다. continue; } check[p.second] = true; answer += -p.first; int x = p.second; for (auto &p : arr[x]) { //연결되는 모든 점의 간선들을 다 넣어준다. q.push(make_pair(-p.second,p.first)); } } printf("%d\n" , answer); | cs |
이렇게 Priority_queue를 사용하게 되면 최소값을 LogE만에 찾을 수 있으므로 시간복잡도가 O(VlogE) ?? O(ElogE)?? 가 된다.
이번에는 크루스칼(Kruskal) 알고리즘에 대해 알아보자. 프림이 정점을 주로 봤다면 크루스칼은 간선에 집중한다.
크루스칼의 핵심은 가중치가 작은 E부터 먼저 살펴본다는 점이다. (해당 부분은 http://kks227.blog.me/220791837179 님의 블로그를 참조하였습니다. 갓 the 블로그)
1. 간선들을 가중치 순으로 오름차순 정렬하고 정점들의 각 컴포넌트를 초기화 한다.
2. 간선들을 훓으면서 양쪽 정점을 포함한 컴포넌트가 연결되어 있지 않으면 간선을 뽑고 , 연결한다.
3. 간선 V-1개가 뽑히는 순간 MST 완성. 즉 종료
영문 위키에 있는 예제를 보도록 하자.
그림이 크다. 하지만 잘 알아볼 수 있을 것이다 ㅋㅋㅋ.....
해당 방식으로 구현을 하게된다면 그리디(Greedy) 측면으로도 볼 수 있을것이고 , V-1번째로 뽑힌 간선의 가중치가 바로 MST를 이루는 간선중 가장 큰 가중치를 가지게 되는 경우이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | int find(int x){ if(x == parent[x]){ return x; }else{ return parent[x] = find(parent[x]); } } void Union(int x,int y){ x = find(x); y = find(y); parent[x] = y; } | cs |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | for (int i=1; i<=num; i++) { parent[i] = i; } vector<pair<int,pair<int,int>>> arr; for (int i=0; i<line; i++) { int a,b,c; scanf("%d %d %d" , &a,&b,&c); arr.push_back(make_pair(c,make_pair(a,b))); //가장 앞에는 가중치 second에는 출발,끝 } sort(arr.begin(),arr.end()); //정렬 long long int answer = 0; for(int i=0;i<line;i++){ auto p = arr[i]; int x = find(p.second.first); int y = find(p.second.second); if (x != y) { //두 부모가 다르면 Union(p.second.first, p.second.second); //합쳐준다. answer += p.first; } } | cs |
와 같이 코딩할 수 있다.
여기서 주의할점 !!! 마지막 for문에서 보통 반복을( i=1;i<=line ;i++) 처럼 1부터 시작하는 경우가 있는데.... 0부터 시작이다 !!
'코딩 > 자료구조&알고리즘' 카테고리의 다른 글
lower_bound, upper_bound 의 차이 (0) | 2017.08.24 |
---|---|
다익스트라(Dijkstra) 알고리즘 - 최단거리 (0) | 2017.03.29 |
Set & MultiSet (2) | 2017.03.06 |
LIS(Longest Increasing Subsequence) - 최장 증가 수열 (1) | 2017.03.06 |
위상정렬(Topolosical Sort) (0) | 2017.02.24 |