DISJOINT-SETS, MST

MST(최소 신장 트리)

MST의 목적

• 낭비를 줄이고 최적의 비용으로 모두를 연결하기 위함
• 그리디한 기법을 쓴다.
• 팩토리얼 보다 적게 만들기 위해서 쓴다.
• 모든 경로의 합이 최소를 찾기 위해서 쓴다.(나중에 나올 다익스트라와 용도가 다르다.)

MST를 만들기 위한 기법은 두가지

• 프림, 크루스칼
• 프림
  • disjoint-sets을 기반으로 깔고 들어간다.
• 크루스칼
  • 크루스칼에서 다음 노드를 선택했을 때 그 노드를 union한다. 또한 사이클이 발생할 수 있는 경우를 방지한다.
  • 트리이기 때문에 사이클이 발생하지 않아야 한다.
  • 간선이 많으면 터진다.

간선이 적으면 크루스칼, 간선이 많으면 프림

 

 

---

 

 

DISJOINT-SETS

 

서로소 집합을 의미한다.

각 집합의 부모 노드를 가지고 있고 부모 노드가 다르면 다른 집합을 의미한다.

 

 

• 그룹의 대표자를 만드는 Union

void union(int x, int y) {
    int a = find(x);
    int b = find(y);

    if(a!=b)
        parent[b] = a;
}

union을 조금 더 효율적으로 사용하고 싶다면 size를 도입하여 size 작은 것을 size큰 쪽에 합치는 형식으로 사용하면 된다.

// 사용하주기 전에 먼저 모든 사이즈를 1로 초기화해준다.
for(int i = 0; i <= n; i++) size[i] = 1;

void union(int x, int y) {
  int a = find(x);
  int b = find(y);

  if(size[a] < size[b]) swap(a,b);
  size[a] += size[b];
  parent[b] = a;
}

 

• 대표자를 찾는 Find

  int find(int x) {
    while(x != parent[x])
      x = parent[x];
    return x;
  }
  
  // 경로 압축(Path compression)
  static int find(int x) {
        // 배열칸에 들어있는 값이 자신과 같으면 대표.
        if(x == disjoint[x]) return x; 
        // 아니면 최종 대표의 값을 배열에 넣어준다.
        return disjoint[x] = find(disjoint[x]); 
    }

   

 

약간 다른 방법으로 하는 union-find

void makeSet() {
	for(int i = 0; i <= N; i++) {
    	p[i] = -1;
    }
}

int find(int x) {
	if(p[x] < 0) return x;
    return p[x] = find(p[x]);
}

void union(int x, int y) {
	int a = find(x);
    int b = find(y);
    if(a==b) return;
    p[a]+=p[b];
    p[b]=a;
}

이렇게 하면 부모의 값에 크기가 들어가 있고 그 외에는 부모를 가리키는 값을 가진다.

 

 

---

 

 

union find를 이용한 크루스칼 알고리즘

• 크루스칼 알고리즘은 탐욕법 기반으로 간선을 추가해 가면서 최소 신장 트리를 만드는 방법이다.
• 처음에는 그래프의 노드만 포함하고 간선이 하나도 포함되어 있지 않은 상태로 시작한다.
• 그런 다음 간선을 가중치 순으로 하나씩 살펴보면서, 간선을 추가해도 사이클이 생기지 않으면(find) 이를 신장 트리에 추가하는 과정을 반복한다.
• 간선을 하나씩 추가할 때마다 컴포넌트 두 개를 합친다.(union)

• 구현

  • 크루스칼 알고리즘을 구현할 때는 그래프의 표현 방식 중 간선 리스트를 사용하는 것이 편리하다.
  • 첫 번째 단계에서는 간선을 O(mlogm) 시간에 정렬한다.(정렬을 하지 않고 하는 방법에는 우선순위 큐를 사용하는 방법이 있다. 우선순위 큐에 넣고 신장 트리를 만들 때 간선의 개수가 n-1개가 되는 순간 큐를 비우고 종료하면 된다. 이렇게 해서 시간을 줄일 수도 있다.)
  • 두번째 단계에서는 다음 코드와 같이 최소 신장 트리를 만든다.

  for(...) {
    if(!same(a,b)) union(a,b); // 이때 간선을 가중치를 더해주면 최소 값을 구할 수 있다.
  }

  • same과 union함수를 유니온-파인드를 이용하면 크루스칼 알고리즘의 시간 복잡도는 O(mlogn)이 된다.

  boolean same(int a, int b) {
    return find(a) == find(b);
  }

   

---

 

 

프림 알고리즘

• 임의의 노드를 트리에 추가하고, 새로운 노드와 트리를 연결하는 노드 중 가중치가 가장 작은 간선을 선택한다.
• 우선순위 큐를 이용하여 효율적으로 구현할 수 있다.
• 프림 알고리즘의 시간 복잡도는 O(n+mlogm)으로 다익스트라 알고리즘과 같다.
• 다수의 경진 프로그래머가 크루스칼 알고리즘을 선호한다.
• 간선이 많을 때 사용한다.

boolean[] check = new boolean[V];
int[] key = new int[V]; // 현재 선택된 정점들로부터 도달할 수 있는 최소거리
int[] p = new int[V]; // 최소신장트리의 구조를 저장할 배열
Arrays.fill(key, Integer.MAX_VALUE);

// 아무거나 하나 선택! (처음선택되는 친구가 루트이므로, 부모는 없는걸로, 거리는 0인걸로)
p[0] = -1;
key[0] = 0;

// 이미 하나를 골랐으므로 V-1를 고른다.
for(int i = 0; i < V-1 ; i++) {
	int min = Integer.MAX_VALUE;
	int idx = -1;
	// 안골라진 친구들 중에서 key가 가장 작은 친구를 뽑는다.
	for(int j = 0; j < V; j++) {
		if(!check[j] && key[j] < min) {
			idx = j;
			min = key[j];
		}
	}
	// idx: 선택이 안된 정점 중 key가 제일 작은 친구가 들어있다.
	check[idx] = true;
	// idx에서 출발하는 모든 간선에 대해서 key를 업데이트
	for(int j = 0; j < V; j++) {
		// check가 안되어있으면서 간선은 존재하고 그 간선이 key값보다 작다면 key값을 업데이트
		if(!check[j] && adj[idx][j] != 0 && key[j] > adj[idx][j]) {
			key[j] = adj[idx][j];
			p[j] = idx;
		}
	}
}