크러스컬 : 엣지를 오름차순으로 정렬하고, 비용이 최소인 엣지부터 유효한 노드를 찾아나간다. > 엣지를 이용해서 노드를 찾음
프림 : 임의의 노드를 하나 잡고 그 노드를 중심으로 엣지의 최솟값을 찾는다. > 노드를 이용해서 엣지를 찾음
Prim's Algorithm : 2020/09/21 - [개발자/Algorithm] - Prim's Algorithm
1. Spanning subgraph (Spanning subtree)
정의 : 모든 꼭짓점을 포함하는 부분 그래프이다.
위 그림에서 보면 좌측의 그래프는 우측의 노란색으로 표시된 것과 같은 8개의 Spanning subtree를 갖는다.
더 큰 그래프를 보면 아래와 같다.
이 그래프의 특징은 모든 꼭짓점을 포함하도록 변이 이어지나, 순환하지 않는다.
Spanning subgraph 의 종류
Spanning subgraph 가운데 r-정규 그래프인 것을 r-factor라고 한다.
0차 인자 : 꼭짓점 집합 위의 무변 그래프. 즉, 그냥 점 하나... 0차원이다.
1차 인자 : 완벽 부합(Perfect matching)이라고 한다.
2차 인자 이상 : 아래 그래프를 확인하자.
페테르센 그래프에서, 붉은 변들은 1차 인자(완벽 부합)를 이루며, 푸른 변들은 2차 인자를 이룬다.
데자르그 그래프에서, 붉은 색의 변들 · 푸른 색의 변들 · 녹색의 변들은 각각 1차 인자(완벽 부합)를 이룬다.
2. Minimum cost spanning tree
여러 꼭짓점(Node, Vertex)과 각 변(Edge)이 있다. 이 모든 꼭짓점을 연결하는 방법(Spanning subtree)는 무수히 많다. 그 중, 변의 비용이 최소가 되는 경우를 '최소 비용 신장 나무(Minimum cost spanning tree)'라 한다.
이를 증명하려면 '선택 공리'가 필요하다는데... 수학과가 아니니 넘어가도록 한다.
이러한 그래프에서 최소 비용을 찾는 대표적인 알고리즘이 Prim's Algorithm(프림 알고리즘)과 Kruskal' Algorithm(크러스컬 알고리즘)이 있다.
꼭짓점의 개수를 V, 변의 개수를 E라고 할 때,
프림 알고리즘은 Binary heap(이진 힙)을 이용해 O(E log V)의 시간복잡도를 가지고, 그래프가 충분히 빽빽한 경우(E = Ω(V log V))에는 Fibonacci heap(피보나치 힙)을 이용해 훨씬 빠르게 할 수 있다. 이 방법은 복잡도가 O(E + V log V)까지 떨어진다.
또한, 크러스컬 알고리즘은 O (E log V)의 시간 복잡도를 갖는다.
음... 솔직히 무슨 말인지 잘 모르겠다 -_-;; 이진 로그인지, 자연 로그인지, 상용 로그인지 설명도 없고... 수학과면 뭔지 알겠지만... 아마 사용로그 같기는 한데..... 그냥 비교 설명이 잘 된 블로그를 하나 소개한다.
최소비용신장트리(MST), 크루스칼, 프림 알고리즘
신장트리 (Spanning Tree) 일단, 최소비용신장트리를 설명하기전 신장트리가 먼지 알아보자. 신장트리란 트리의 특수한 형태로 그래프의 모든 정점을 포함하면서 그 모든 정점들이 연결되어야 있어
mini-ko.tistory.com
크러스컬 : 엣지를 오름차순으로 정렬하고, 비용이 최소인 엣지부터 유효한 노드를 찾아나간다.
프림 : 임의의 노드를 하나 잡고 그 노드를 중심으로 엣지의 최솟값을 찾는다.
크러스컬은 평균적이고, 프림은 코드를 얼마나 효율적으로 짰는지에 따라 효율이 극대화 되거나 극악이 된다.
이론적으로는 '엣지 >> 노드'인 경우 프림이 훨씬 빠르지만 잘못 짜면 망한다... 그래서 알고리즘 메달리스트들은 크러스컬만 쓴다고...
We can achieve this bound as follows: first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step "remove an edge with minimum weight from S" to operate in constant time. Next, we use a disjoint-set data structure to keep track of which vertices are in which components. We place each vertex into its own disjoint set, which takes O(V) operations. Finally, in worst case, we need to iterate through all edges, and for each edge we need to do two 'find' operations and possibly one union. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(E) operations in O(E log V) time. Thus the total time is O(E log E) = O(E log V).
뭔소리죠...?
코드 최적화... 이 압축하는게 그림으로 볼 때 그래프의 모양(MST)이 바뀌는 것은 아니다. 단, 컴퓨터라 사람처럼 한 눈에 볼 수 없어 '자식 - 부모'의 노드 관계를 구하기 위해서는 '1 - 3 - 5 - 7' 이라는 그래프에서 7의 부모를 찾기 위해서 5를 찾고, 다시 5의 부모가 있는지 찾기 위해서 3을 찾고.. 이런식으로 3번 재귀함수를 돌아야 한다. 이게 꼭짓점이 많아지고, 노드가 일렬로 이어지면 시간복잡도가 매우 높아지기 때문에 재귀에서 return이 될 때 3, 5, 7의 부모를 모두 1이라 업데이트를 해준다.
Kruskal.java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Kruskal {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static PriorityQueue<Edge> pq; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = sc.nextInt();
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = sc.nextInt();
mst = new ArrayList<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
// Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는 '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
pq = new PriorityQueue<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
// 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
arr[i] = i;
}
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
pq.add(new Edge(v1, v2, value));
}
// V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
while(mst.size() < (V-1)) {
// PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
Edge edge = pq.poll();
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
if(find(edge.start)!=find(edge.end))
{
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 MST ArrayList에 Edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(edge.start, edge.end);
}
}
System.out.println(mst);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int n1, int n2) {
int p1 = find(n1); // p1 : n1의 부모, n1 : 앞쪽 인자 node
int p2 = find(n2); // p2 : n2의 부모, n2 : 뒤쪽 인자 node
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}
/*
6
9
1 2 5
1 3 4
2 3 2
2 4 7
3 4 6
4 6 8
3 5 11
4 5 3
5 6 8
*/
// source : https://velog.io/@dudrkdl777/Graph-최소신장트리-MSTKruskal알고리즘수업때 한 원본 소스...
여기서 보면 union 함수 안에
if (p1 != p2) {
arr[p1]= p2;
}이 부분이 Path Compression(경로 압축)을 하는 과정... 즉, 코드 최적화다.
Kruskal2.java
// 기존 1번 코드 원본에서 불필요하게 반복되는 find 함수의 실행을 줄임.
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Kruskal2 {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static PriorityQueue<Edge> pq; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = sc.nextInt();
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = sc.nextInt();
mst = new ArrayList<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
// Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는 '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
pq = new PriorityQueue<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
// 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
arr[i] = i;
}
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
for (int i = 0; i < E; i++) {
int v1 = sc.nextInt(); // 1번 노드와... 1번 노드와
int v2 = sc.nextInt(); // 2번 노드의... 3번 노드의
int value = sc.nextInt(); // 비용은 5다... 비용은 4다
// 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
pq.add(new Edge(v1, v2, value));
}
// V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
while(mst.size() < (V-1)) {
// PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
Edge edge = pq.poll();
// Edge의 양 끝 각 노드(start, end라 명명함)의 최종 부모(root)를 구한다.
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
// int parentEdgeStart = -1;
// int parentEdgeEnd = -1;
// // 기본 변수 타입인 int는 null을 받아들일 수 없다. edge 객체의 int 변수를 Integer로 바꿨다.
// // 의미가 있는지는 모르겠음. 그냥 위에 바로 int에 find 돌려서 넣고 edge 인스턴스 변수는 그대로 int로 해도 될 것 같은데...
// if (edge.start != null && edge.end != null) {
// parentEdgeStart = find(edge.start);
// parentEdgeEnd = find(edge.end);
// }
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
if(parentEdgeStart != parentEdgeEnd)
{
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
// Integer start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}MST를 구할 때마다 union함수 내에서 find 함수를 불필요하게 다시 호출하는 문제가 있어 해당 로직을 줄였다.
Kruskal3.java
// 2번 코드에서 Scanner를 BufferedReader, InputStreamReader로 바꿈.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
public class Kruskal3 {
static int V, E; // V : 점, E : 변
static ArrayList<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static PriorityQueue<Edge> pq; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
// throws IOException을 해주거나,
// String var = null; 을 미리 인스턴스화 시킨 후
// try {
// var = bufferedReader.readLine();
// } catch (IOException | NumberFormatException e) {
// e.printStackTrace();
// }
// 을 해줘야한다.
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = Integer.parseInt(bufferedReader.readLine());
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = Integer.parseInt(bufferedReader.readLine());
mst = new ArrayList<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
// Queue는 기본적으로 FIFO 구조를 갖는다. Priority queue는 '최대 우선순위 큐'와 '최소 우선순위 큐'로 나뉜다.
pq = new PriorityQueue<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
// 각 vertex는 시작할 때는 자기 자신을 root로 초기화.
arr[i] = i;
}
// Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
String[] inputTmp = new String[3];
int v1;
int v2;
int value;
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
for (int i = 0; i < E; i++) {
inputTmp = bufferedReader.readLine().split(" ");
v1 = Integer.parseInt(inputTmp[0]); // 1번 노드와... 1번 노드와
v2 = Integer.parseInt(inputTmp[1]); // 2번 노드의... 3번 노드의
value = Integer.parseInt(inputTmp[2]); // 비용은 5다... 비용은 4다
// 우선순위 큐에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
pq.add(new Edge(v1, v2, value));
}
// V개의 노드를 연결하는 최소 Edge의 수는 '노드-1'이므로 mst.size()가 'V-1'이 될 때까지 반복한다.
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
while(mst.size() < (V-1)) {
// PQ에 하나씩 넣었고, 이제 하나씩 뺀다. PQ로 넣어서 FIFO이 아닌 오름차순으로 나온다.(value 기준)
Edge edge = pq.poll();
// Edge의 양 끝 각 노드(start, end라 명명함)의 최종 부모(root)를 구한다.
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
// int parentEdgeStart = -1;
// int parentEdgeEnd = -1;
// // 기본 변수 타입인 int는 null을 받아들일 수 없다. edge 객체의 int 변수를 Integer로 바꿨다.
// // 의미가 있는지는 모르겠음. 그냥 위에 바로 int에 find 돌려서 넣고 edge 인스턴스 변수는 그대로 int로 해도 될 것 같은데...
// if (edge.start != null && edge.end != null) {
// parentEdgeStart = find(edge.start);
// parentEdgeEnd = find(edge.end);
// }
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
if(parentEdgeStart != parentEdgeEnd)
{
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
bufferedReader.close();
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
// Integer start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) {
return this.value - o.value;
}
@Override
public String toString() {
return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n";
}
}
}위 2번 코드에서 Scanner를 BufferedReader, InputStreamReader로 바꿨다.
Kruskal4.java
더보기
// 3번 코드에서 ArrayList<Edge> mst를 HashSet<Edge>로, PriorityQueue<Edge> pq를 TreeSet<Edge>로 바꿈.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.TreeSet;
public class Kruskal4 {
static int V, E; // V : 점, E : 변
static HashSet<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static TreeSet<Edge> ts; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = Integer.parseInt(bufferedReader.readLine());
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = Integer.parseInt(bufferedReader.readLine());
mst = new HashSet<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
ts = new TreeSet();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
arr[i] = i;
}
// Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
String[] inputTmp = new String[3];
int v1;
int v2;
int value;
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
for (int i = 0; i < E; i++) {
inputTmp = bufferedReader.readLine().split(" ");
v1 = Integer.parseInt(inputTmp[0]); // 1번 노드와... 1번 노드와
v2 = Integer.parseInt(inputTmp[1]); // 2번 노드의... 3번 노드의
value = Integer.parseInt(inputTmp[2]); // 비용은 5다... 비용은 4다
// TreeSet에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
ts.add(new Edge(v1, v2, value));
}
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
while(mst.size() < (V-1)) {
// TreeSet 잘 될까!?
Edge edge = ts.pollFirst();
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
if(parentEdgeStart != parentEdgeEnd) {
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
bufferedReader.close();
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) { return this.value - o.value; }
@Override
public String toString() { return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n"; }
}
}3번 코드에서 ArrayList<Edge> mst를 HashSet<Edge>로, PriorityQueue<Edge> pq를 TreeSet<Edge>로 바꿨다.
Kruskal5.java
더보기
// 3번 코드에서 ArrayList<Edge> mst와 PriorityQueue<Edge> pq를 모두 TreeSet<Edge>로 바꿈.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;
public class Kruskal5 {
static int V, E; // V : 점, E : 변
static TreeSet<Edge> mst; // result값 Minimum spanning tree
static int[] arr ; // 각 노드의 부모가 누구인지를 저장한다. ex) arr[0] = 1 이면 0의 부모(root node)는 1이다.
static TreeSet<Edge> ts; // 모든 노드(점)을 힙에 넣고 시작.
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
long startTime = System.nanoTime();
// Vertex : 전체 점의 개수를 입력 받는다. (샘플에서 6에 해당)
V = Integer.parseInt(bufferedReader.readLine());
// Edge : 전체 변의 개수를 입력 받는다. (샘플에서 9에 해당)
E = Integer.parseInt(bufferedReader.readLine());
mst = new TreeSet<>();
arr = new int[V+1]; // array는 인덱스가 0부터 시작하는데 문제의 점이 1부터 6까지라 인덱스 0번을 제외하고 1~6을 쓰기 위헤 V+1개의 배열 생성.
ts = new TreeSet<>();
// vertex의 개수 + 1개 만큼 반복. (i = 1부터 시작하면 안 된다. 0번을 안 쓰더라도 배열은 반드시 0번부터 채워야한다. 비워둘 수 없다.)
for (int i = 0; i <= V; i++) {
arr[i] = i;
}
// Edge의 정보는 양쪽 Vertex와 비용, 3개의 정보만 고정적으로 존재하기 때문에 3으로 고정 선언.
String[] inputTmp = new String[3];
int v1;
int v2;
int value;
// 각 노드의 연결 관계와 비용을 입력 받는다. (샘플에서 1 2 5... 1 3 4 에 해당)
// 즉, mst.size()가 'V-2'개일 때 반복하다, 마지막 하나를 더 찾아 'V-1'개가 되면 반복문 조건이 false가 된다.
for (int i = 0; i < E; i++) {
inputTmp = bufferedReader.readLine().split(" ");
v1 = Integer.parseInt(inputTmp[0]); // 1번 노드와... 1번 노드와
v2 = Integer.parseInt(inputTmp[1]); // 2번 노드의... 3번 노드의
value = Integer.parseInt(inputTmp[2]); // 비용은 5다... 비용은 4다
// TreeSet에 Edge라는 객체를 하나씩 추가한다. Edge는 변으로, 자기 자신의 좌우의 노드와 비용에 대한 정보를 갖는다.
ts.add(new Edge(v1, v2, value));
}
// Edge(변)의 앞뒤 각각 노드의 최종 부모가 서로 같지 않다면(= 서로 다른 그룹이라면 혹은 아직 그룹이 아니라면) 실행. (Edge의 좌우 노드의 최종 부모가 같다면 이미 같은 그룹이니 해당 엣지는 로직을 돌지 않고 버린다.)
while(mst.size() < (V-1)) {
// TreeSet 잘 될까!?
Edge edge = ts.pollFirst();
int parentEdgeStart = find(edge.start);
int parentEdgeEnd = find(edge.end);
if(parentEdgeStart != parentEdgeEnd) {
// 같은 그룹이 아니라면 MST 로직을 만족(True)하니까 mst ArrayList에 edge 객체를 추가한다.
mst.add(edge);
// MST에 추가한 후 이 Edge가 속한 그룹(Union)이 새 그룹이든, 기존 그룹에 결합된 그룹이든간에 Edge 객체의 좌우 노드의 최종 부모(root)를 갱신해준다.
union(parentEdgeStart, parentEdgeEnd);
}
}
bufferedReader.close();
System.out.println(mst);
long endTime = System.nanoTime(); // (종료점)
long timeInterval = (endTime - startTime) / 1000000; // (시간차)
System.out.printf("Code Time : %d (ms) \n", timeInterval);
}
static int find(int n) { // 입력 받은 노드의 최종 부모를 구한다.
if (n == arr[n]) { // 자기 자신이 root면 자기 자신을 반환. root가 바뀌어 자기 자신이 root가 아니면 자신의 부모 노드가 root인지를 재귀를 통해 확인. 이 경우 아래 else문을 탄다.
return n;
} else {
int p = find(arr[n]); // 각 노드의 부모를 찾는 함수를 재귀로 호출한다. 자기 자신이 root가 되어 if문을 탈 때까지 재귀를 반복한다. 재귀를 돌 때 arr[n]을 넣어 자기의 부모를 넣는다.
// 그러면 그 부모는 또 자기의 부모를 찾는다. 그리고 더이상 부모가 없고 자기 자신이 root면 return을 한다. // ex) arr[0] = 1, arr[1] = 5, arr[5] = 5 자기 자신인 최종 root가 나오면 3번 호출되어 if문을 타고 return된다.
arr[n]=p; // path compression : 코드 최적화. 불필요한 재귀 호출을 줄이기 위해 재귀를 들어가 return 되어 나올 때 각 노드의 최종 부모(root)를 가리키도록 저장한다.
// 즉, arr[0] = 3, arr[1] = 3, arr[5] = 3. 그러면 다음번에는 1+1번만 호출되어 return된다.
return p; // 최종 부모(root)를 return.
}
}
// Union 로직 함수. 노드1과 노드2의 최종 부모가 다르다면 같은 그룹이 아니므로 하나의 그룹으로 결합한다. 이 때 root는 뒤쪽 노드가 된다.
static void union(int p1, int p2) {
if (p1 != p2) {
arr[p1]= p2;
}
}
// Edge 객체를 클래스로 정의. 2개의 노드와 1개의 비용을 변수로 갖는다.
static class Edge implements Comparable<Edge>{
int start, end, value;
Edge(int s, int e, int v) {
this.start = s;
this.end = e;
this.value = v;
}
@Override
public int compareTo(Edge o) { return this.value - o.value; }
@Override
public String toString() { return "Edge [start=" + start + ", end=" + end + ", value=" + value + "]\n"; }
}
}3번 코드에서 ArrayList<Edge> mst와 PriorityQueue<Edge> pq를 모두 TreeSet<Edge>로 바꿨다.
참고 : 2 ~ 5번 코드에 보면 시간 측정 로직이 들어갔는데, 시작시간이 내가 지정한 시점에서 시작되지 않고, new Scanner(System.in);나 new BufferedReader(new InputStreamReader(System.in)); 이쪽에서 System.in이 시작된 때의 시간을 가져와서 제대로 된 시간 측정이 되지 않는다.
읽어보면 좋은 자료
자료구조 힙(heap)
Reference
ko.wikipedia.org/wiki/신장_부분_그래프
신장 부분 그래프 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 그래프의 신장 부분 나무 그래프 왼쪽의 그래프는 오른쪽과 같이 총 8개의 신장 부분 나무 그래프들을 갖는다. 그래프 이론에서, 신장 부분 그래프(身長部分grap
ko.wikipedia.org
ko.wikipedia.org/wiki/크러스컬_알고리즘
크러스컬 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 크러스컬 알고리즘(영어: Kruskal’s algorithm)은 최소 비용 신장 부분 그래프를 찾는 알고리즘이다. 변의 개수를 E {\displaystyle E} , 꼭짓점의 개수�
ko.wikipedia.org
프림 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소
ko.wikipedia.org
Tag.
bufferedreader, buffered reader, Buffered Reader, 버퍼드리더, 버퍼드 리더, inputstreamreader, input stream reader, inputstream reader, Input Stream Reader, 인풋스트림리더, 인풋 스트림 리더, 인풋스트림 리더, 크러스컬 알고리즘, 크루스칼 알고리즘, kruskal algorithm, kruskal's algorithm, kruskal's, 프림 알고리즘, prim's algorithm, prim's, prim algorithm, Prim Algorithm, Prim's Algorithm
'개발자 > Algorithm' 카테고리의 다른 글
| Kruskal & Prim 비교 (0) | 2020.09.22 |
|---|---|
| Prim's Algorithm (0) | 2020.09.21 |
| 05. 장기판 포 말잡기 (0) | 2020.08.30 |
| 04. 토끼 잡기 (0) | 2020.08.28 |
| 02. 수열 A와 수열 B가 같은지 확인하기 (0) | 2020.08.24 |