-
[알고리즘 정리] Kruskal & Prim(크루스칼과 프림)Development/Algorithm 2020. 5. 3. 20:59
다룰 내용
- 신장 트리란 무엇인가?
- 최소 비용 신장 트리란 무엇인가?
- 최소 비용 신장 트리를 구성하는 방법
- Kruskal 알고리즘
- Prim 알고리즘
신장 트리란 무엇인가?
그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리를 말합니다.
사이클이 안 생기는 조건 안에서 간선의 개수를 정점 - 1개로 골라 만드는 것으로, 정점 - 1의 수가 간선의 수가 되는 트리입니다.
최소 비용 신장 트리란 무엇인가?
신장 트리 중에서 간선들의 합이 최소인 트리입니다. 또한 무향 가중 그래프에서 만들어질 수 있고 사이클이 발생되지 않으며 비용의 합이 최소인 트리입니다.
최소 비용 신장 트리의 특징
- 무방향 가중치 그래프입니다.
- 가중치의 합이 최소입니다.
- 정점 n개에서 n - 1개의 간선을 가지는 트리입니다.
- 사이클이 포함되서는 안됩니다.
최소 비용 신장 트리의 사용
도로망, 통신망, 유통망 등 여러 분야에서 비용을 최소로 해야하는 경우에 유용하게 사용됩니다.
최소 비용 신장 트리를 구성하는 방법
- Kruskal(크루스칼 알고리즘)
- Prim(프림 알고리즘)
Kruskal 알고리즘
간선 선택 기반의 알고리즘으로, 탐욕적인 방법을 이용, 간선을 하나씩 선택해서 MST를 찾는 알고리즘입니다.
크루스칼 알고리즘 동작 과정
- 그래프의 간선들을 가중치의 오름차순으로 정렬
- 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택합니다.
- 이때 가중치가 가장 낮은 간선을 선택합니다.
- 사이클이 형성되는 간선이라면 다음 간선을 선택합니다.
- 선택한 간선을 MST 집합에 추가 (n - 1)개의 간선이 선택될 때까지 반복 수행합니다.
import java.io.*; import java.util.*; public class Kruskal { // 정점의 부모 노드를 저장할 배열 public static int parents[]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input1[] = br.readLine().split(" "); int V = Integer.parseInt(input1[0]); // 정점의 개수 int E = Integer.parseInt(input1[1]); // 간선의 개수 // 정점의 정보 2개 + 이들의 가중치 순으로 입력이 들어옴. int edges[][] = new int[E][3]; // 1번부터 인덱스를 사용하기 위해서 V + 1 parents = new int[V + 1]; // 간선의 정보와 가중치 입력 받기 for(int i = 0; i < E; i++) { String input2[] = br.readLine().split(" "); edges[i][0] = Integer.parseInt(input2[0]); // 정점1 edges[i][1] = Integer.parseInt(input2[1]); // 정점2 edges[i][2] = Integer.parseInt(input2[2]); // 가중치 } // 가중치 오름차순으로 정렬 Arrays.sort(edges, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { // 2번째 인덱스에 가중치가 있으므로 가중치를 기준으로 오름차순 정렬 return Integer.compare(o1[2], o2[2]); } }); // parents를 -1로 초기화 Arrays.fill(parents, -1); // 출력될 가중치의 합 int result = 0; int cnt = 0; // 간선의 수만큼 loop 수행 for(int i = 0; i < edges.length; i++) { // 정점과 정점이 연결될 수 있는지 확인 if(union(edges[i][0], edges[i][1])) { result += edges[i][2]; // 가중치 덧셈 cnt++; } // cnt가 정점 - 1개가 된다는 것은 모든 정점을 다 연결했다는 의미이므로 종료 if(cnt == V - 1) break; } System.out.println(result); } public static int find(int x) { if(parents[x] < 0) return x; return parents[x] = find(parents[x]); } public static boolean union(int x, int y) { int xRoot = find(x); // x의 root를 찾아서 결과 받음 int yRoot = find(y); // y의 root를 찾아서 결과 받음 // 두 개의 정점의 root가 같지 않다면 같은 집합에 속하지 않은 것 if(xRoot != yRoot) { parents[yRoot] = xRoot; // 따라서 y의 root를 x의 root로 변경 return true; // 연결되었으므로 true return } // 연결을 하지 못한 경우이므로 false return return false; } }
Prim 알고리즘
정점 선택 기반의 알고리즘으로, 하나의 정점에서 연결된 간선들 중에 최소 간선 비용을 가진 정점을 하나씩 선택하면서 MST를 찾는 알고리즘
프림 알고리즘 동작 과정
- 임의의 정점 하나를 선택해서 시작합니다.
- 선택한 정점과 인접하는 정점들 중에 최소 비용의 간선을 가지는 정점을 선택합니다.
- 모든 정점이 선택될 때까지 반복합니다.
프림의 경우 선택된 정점들과 연결된, 선택되지 않은 정점들의 간선에서 최소 간선 비용을 가진 정점을 선택하는 방식으로 진행됩니다.
Prim + 인접 행렬
import java.io.*; import java.util.Arrays; public class Prim { /* * 간선이 많은 경우 Prim이 유리하고 * 인접행렬을 사용하는 것이 유용함 * 프림 + 인접행렬 궁합 좋음 */ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input1[] = br.readLine().split(" "); int V = Integer.parseInt(input1[0]); // 정점의 개수 int E = Integer.parseInt(input1[1]); // 간선의 개수 // 정점의 정보 2개 + 이들의 가중치 순으로 입력이 들어옴. int adj[][] = new int[V][V]; int result = 0; // 간선의 정보와 가중치 입력 받기 for(int i = 0; i < E; i++) { String input2[] = br.readLine().split(" "); int a = Integer.parseInt(input2[0]) - 1; int b = Integer.parseInt(input2[1]) - 1; int c = Integer.parseInt(input2[2]); // 인접 행렬 구성 adj[a][b] = c; adj[b][a] = c; } // 선택되었는지 아닌지 판단하기 위한 boolean 배열 boolean visited[] = new boolean[V]; // 현재 선택된 정점들로부터 도달할 수 있는 최소 거리 저장 배열 int distance[] = new int[V]; // 모두 최대 값으로 key를 갱신 Arrays.fill(distance, Integer.MAX_VALUE); distance[0] = 0; // 처음 선택한 정점은 거리 0 int cnt = 0; while(true) { int min = Integer.MAX_VALUE; int idx = 0; for(int i = 0; i < V; i++) { // 선택되지 않았고 거리를 저장한 key보다 작은 경우 갱신 if(!visited[i] && distance[i] < min) { idx = i; min = distance[i]; } } // 선택된 정점에 포함시킴 visited[idx] = true; // 결과값에 가중치 덧셈 result += min; cnt++; // cnt가 V랑 같아지면 모든 정점을 처리한 것이므로 종료 if(cnt == V) break; // 새로 추가한 정점으로부터 연결되어 있는 다른 정점의 간선 정보 업데이트 for(int i = 0; i < V; i++) { if(!visited[i] && adj[idx][i] > 0 && distance[i] > adj[idx][i]) { distance[i] = adj[idx][i]; } } } System.out.println(result); } }
Prim + PQ(Priority Queue)
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.PriorityQueue; public class Prim_pq { public static class Vertex implements Comparable<Vertex>{ int v, dist; Vertex(int v, int dist){ this.v = v; this.dist = dist; } @Override public int compareTo(Vertex o) { return Integer.compare(this.dist, o.dist); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input1[] = br.readLine().split(" "); int V = Integer.parseInt(input1[0]); int E = Integer.parseInt(input1[1]); int result = 0; List<Vertex> list[] = new ArrayList[V]; for(int i = 0; i < V; i++) list[i] = new ArrayList<Vertex>(); // 간선의 정보와 가중치 입력 받기 for(int i = 0; i < E; i++) { String input2[] = br.readLine().split(" "); int a = Integer.parseInt(input2[0]) - 1; int b = Integer.parseInt(input2[1]) - 1; int c = Integer.parseInt(input2[2]); // 인접 리스트 구성 list[a].add(new Vertex(b, c)); list[b].add(new Vertex(a, c)); } // 선택되었는지 아닌지 판단하기 위한 boolean 배열 boolean visited[] = new boolean[V]; // 현재 선택된 정점들로부터 도달할 수 있는 최소 거리 저장 배열 int distance[] = new int[V]; // 모두 최대 값으로 key를 갱신 Arrays.fill(distance, Integer.MAX_VALUE); distance[0] = 0; // 처음 선택한 정점은 거리 0 int cnt = 0; PriorityQueue<Vertex> q = new PriorityQueue<Vertex>(); q.offer(new Vertex(0, distance[0])); while(true) { Vertex cur = q.poll(); if(visited[cur.v]) continue; visited[cur.v] = true; result += cur.dist; cnt++; if(cnt == V) break; for(Vertex v : list[cur.v]) { if(!visited[v.v] && distance[v.v] > v.dist) { distance[v.v] = v.dist; q.offer(new Vertex(v.v, distance[v.v])); } } } System.out.println(result); } }
'Development > Algorithm' 카테고리의 다른 글
[알고리즘 정리] KMP, 문자열 패턴 매칭 알고리즘 (0) 2020.05.04 [알고리즘 정리] Dijkstra(다익스트라) (0) 2020.05.03 [알고리즘 정리] 조합, 부분 집합 구현 (0) 2020.05.03 [알고리즘 정리] Union-Find(유니온 파인드) (0) 2020.05.03 [알고리즘 정리] 순열, next_permutation 구현 (0) 2020.04.29