728x90
반응형
신장트리(Spanning Tree)는 그래프 내의 모든 정점을 포함하는 트리입니다. MST(Minimum Spanning Tree)는 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리를 이야기합니다. MST는 크루스칼 그리고 프림 알고리즘이 있습니다. 여기서는 프림알고리즘을 다루겠습니다.
- 그래프 내의 간선의 숫자가 적은 희소 그래프의 경우 : 크루스칼 알고리즘
- 그래프 내의 간선의 숫자가 많은 밀집 그래프의 경우 : 프림 알고리즘
동작방식
시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해 나가는 방법
- 시작 단계에서는 시작 정점만이 MST 에 포함합니다.
- 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장합니다.
- 즉, 가장 낮은 가중치를 먼저 선택합니다.
- 위의 과정을 트리가 N-1 개의 간선을 가질 때까지 반복합니다.
시간복잡도
기본적으로 O(N^2) 의 시간복잡도를 가지고 있습니다. 우선순위 큐를 사용한다면 O( E logV)의 시간복잡도를 가집니다.
참고사이트
https://hibee.tistory.com/300
[AL] 7. 최소 비용 신장 트리(MST) 알고리즘
7. 최소 비용 신장 트리(MST) 알고리즘 신장 트리 (Spanning Tree) 최소 비용 신장 트리 (MST) Kruskal MST 알고리즘 Prim MST 알고리즘 1. 신장 트리 (Spanning Tree) 1.1. Spanning Tree 그래프..
hibee.tistory.com
기본코드
| 7 11 1 2 2 2 3 5 1 3 20 1 4 10 4 5 1 5 6 23 3 6 3 3 5 6 7 6 9 7 3 2 2 7 7 |
package study.graph;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
class B implements Comparable<B>{
int n;
int dist;
B (int a, int b){
this.n = a;
this.dist = b;
}
@Override
public int compareTo(B tar) {
if(tar.dist < this.dist) return 1;
if(tar.dist > this.dist) return -1;
return 0;
}
}
public class MST_프림 {
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("input\\prim.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
int M = Integer.parseInt(br.readLine());
int[] used = new int[N+1]; // 방문 여부 (0: 미방문, 1: 방문)
ArrayList<ArrayList<B>> alist = new ArrayList<ArrayList<B>>();
for(int i=0; i<=N; i++) {
alist.add(new ArrayList<B>());
}
StringTokenizer st = null;
for(int m=1; m<=M; m++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int dist = Integer.parseInt(st.nextToken());
alist.get(a).add(new B(b, dist));
alist.get(b).add(new B(a, dist));
}
PriorityQueue<B> pq = new PriorityQueue<B>();
Queue<Integer> q = new LinkedList<Integer>();
q.add(1); // 임의의 한 노드를 지정
int sumDist = 0;
while(!q.isEmpty()) {
int currentNode = q.poll();
used[currentNode] = 1; // 방문표시
// 현재 노드에 연결된 간선을 pq에 넣음(방문한 노드는 제외)
for(int i=0; i<alist.get(currentNode).size(); i++) {
if(used[alist.get(currentNode).get(i).n] != 1) {
pq.add(alist.get(currentNode).get(i));
}
}
while(!pq.isEmpty()) {
B tar = pq.poll();
if(used[tar.n] == 1) continue; // 방문한 노드면 pass
used[tar.n]= 1;// 방문표시
sumDist += tar.dist;
q.add(tar.n); // 연결된 노드를 큐에 넣어줌
break; // pq에서 방문하지 않은 노드로 가는 가장 dist가 작은 것을 석택해주었으니 여기서 멈춤
}
}
bw.write("# " + sumDist);
bw.close();
br.close();
}
}728x90
반응형
