[Kruskal, Prim 알고리즘] 서로소 집합, 최소 신장 트리 자바로 구현하기

Disjoint-set

- 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다.

- 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.

- 서로소 집합을 표현하는 방법 : 연결리스트, 트리

- 서로소 집합 연산 : Make-Set(x), Find-Set(x), Union(x, y)

 

연결 리스트

- 같은 집합의 원소들은 하나의 연결리스트로 관리한다.

- 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.

- 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.

 

트리

- 같은 집합의 원소들을 하나의 트리로 표현한다.

- 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

 

 

트리의 배열을 이용하면 아래와 같다.

 

 

자바로 나타내보기

public class DisjoinSetTest {
	static int N = 5;
    static int[] parents;
    
    static void make() {
    	for(int i=0; i < N; i++;) {
        	parents[i] = i; //자신의 부모를 자신으로하여 대표자가 되도록 설정
        }
    }
    static int findSet(int a) {
        if(a==parents[a]) return a; // 자신이 자신의 부모라면 루트노드이고 집합의 대표자가 됨
        return findSet(parents[a]);
    }
    static boolean union(int a, int b) {
    	int aRoot = findSet(a);
        int bRoot = findSet(b);
        if(aRoot == bRoot) return false; //두 집합의 대표자가 같으면 이미 같은 집합이므로 합집합 연산 불가
        // 두 집합 합치기
        parents[bRoot] = aRoot;
        return true;
    }
}

 

최적화

문제점

결국에는 재귀를 사용하기 때문에 메모리나 시간 효율성 면에서 떨어진다

 

연산의 효율을 높이는 방법

Rank를 이용한 Union

- 각 노드는 자신을 루트로 하는 서브트리의 높이를 rank로 저장한다.

- 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.

 

Path compression

- Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다

 

 

 

최소 신장 트리 (MST)

그래프에서 최소 비용 문제

1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리

2. 두 정점 사이의 최소 비용의 경로 찾기

 

신장 트리

- n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

 

최소 신장 트리

- 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

Kruskal 알고리즘

간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬

2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴

- 사이클이 존재하면 남아 있는 간선 중 그 다음으로 가중치가 낮은 간선 선택

3. n-1 개의 선택될 때까지 2를 반복

 

자바로 코드구현!

public class MST_KruskalTest {
	static int V = 5;
    static int[] parents;
    
    static void make() {
    	for(int i=0; i < N; i++;) {
        	parents[i] = -1;
        }
    }
    static int findSet(int a) {
        if(parents[a] < 0) return a; // 자신이 자신의 부모라면 루트노드이고 집합의 대표자가 됨
        return parents[a] = findSet(parents[a]); //집합의 대표자를 자신의 부모로 변경: path 압축!
    }
    static boolean union(int a, int b) {
    	int aRoot = findSet(a);
        int bRoot = findSet(b);
        if(aRoot == bRoot) return false; // 두 집합의 대표자가 같으면 이미 같은 집합이므로 합집합 연산 불가
        // 편의상 a집합에 b집합을 붙임(집합의 크기에 따라 붙이도록 처리도 가능)
        parents[aRoot] += parents[bRoot]; // 집합 크기 관리 (절대값을 사용하면 집합의 크기가 됨) 
        parents[bRoot] = aRoot;
        return true;
    }
    
    static class Edge implements Comparable<Edge> {
    	int start, end, weight;
        pubic Edge(int start, int end, int weight) {
        	this.start = start;
            this.end = end;
            this.weight = weight;
        }
        @Override
        public int compareTo(Edge o) {
        	return Integer.compare(this.weight, o.weight);
        }
    }
}

 

이렇게 함수 구현 후 가중치를 이용한 오름차순 정렬을 하고 더해주면 된다.

 

 

Prim 알고리즘

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

1. 임의 정점을 하나 선택해서 시작

2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택

3. 모든 정점이 선택될 때 까지 2과정을 반복

 

서로소인 2개의 집합 정보를 유지

- 트리 정점들 - MST를 만들기 위해 선택된 정점들

- 비트리 정점들 - 선택 되지 않은 정점들

 

int V = sc.nextIt() //정점수
int[][] adjMatrix = new int[V][V];
boolean[] visited = new boolean[V] // 방문여부 배열(트리 포함정점배열)
int[] midEdge = new int [V] //자신과 타정점들간의 간선비용 중 최소 간선 비용

for(int i=0; i<V; i++) {
	for(int j=0; j<V; j++){
		adjMatrix[i][j] = sc.nextInt();
    }
}

Arrays.fill(minEdge, Integer.MAX_VALUE);
minEdge[0] = 0; //0번 정점을 트리의 시작정점이 되도록 함(다른 정점이어도 상관없음)
int cost = 0;

for(int i=0; i<V; i++) {
	// step1: 트리 구성에 포함될 가장 유리한 정점 선택(비트리 정점 중 최소비용 간선의 정점 선택)
    int min = Integer.MAX_VALUE;
    int minVertex = -1;
    for(int j=0; j<V; j++) {
    	if(visited[j]) continue;
        if(min>minEdge[j]) {
        	minVertex = j;
            min = minEdge[j];
        }
    }
	if(minVertex == -1) break;
    visited[minVertex] = true;
    cost +=min;
    
    // step2: 선택된 정점과 타 정점들 간선비용 비교하기 (간보기)
    for(int j=0; j<V; j++) {
        if(!visited[j] && adjMatrix[minVertex][j] >0 && minEdge[j] > adjMatrix[minVertex][j]) {
        	minEdge[j] = adjMattrix[minVertex][j];
        }
    }
}

 

 

PriorityQueue로 구현

우선순위 큐를 구현하는 가장 효율적인 방법이 힙을 사용하는 것이다.

- 노드 하나의 추가/삭제의 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수있다.

- 완전 정렬보다 관리 비용이 적다.

 

배열을 통해 트리 형태를 쉽게 구현할 수 있다.

- 부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다.

- n위치에 있는 노드의 자식은 2n과 2n+1위치에 존재한다.

- 완전 이진 트리의 특성에 의해 추가/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다.

 

java.utill.priorityQueue()

- 원소들의 natural Ordering에 따라 Heap 유지

- 따라서, 반드시 모든 원소는 Comparable 인터페이스를 구현해야 한다.

 

힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행된다.

 

정렬을 위한 2단계

1. 하나의 값에 힙을 삽입한다.

2. 힙에서 순차적으로 값을 하나씩 제거한다.

 

힙정렬의 시간 복잡도

- N개의 노드 삽입 연산 + N개의 노드 삭제 연산

- 노드 하나의 삽입과 삭제 연산은 각각 O(logN)이다.

- 따라서 전체 정렬은 O(NlogN)이다.

 

우선순위큐로 프림 알고리즘 구현