Tag Archives: Algorithms

[Java] Weighted Quick Union Algorithms + Path Compression

Weighted Quick Union 알고리즘에, Path Compression을 더했다.
어차피 연결되어 있는지 여부만 찾는 것이기 때문에 (최단거리를 찾는 것이 아니다)
불필요하게 길어진 트리노드를 압축하는 방식이다.
id[i] = id[id[i]];
이 한줄을 추가함으로써, 노드와 노드가 길게 붙어가는 것이 아니라, 좀더 짧게 연결되므로써 트리의 길이를 줄게 하는 효과를 가지고 있다.

import java.util.Arrays;
import java.util.Scanner;

public class Weighted_Quick_Union {

	private static int[] id;
	private static int[] sz;

	public static void main(String[] args) {

		initArray(10);

		union(1, 7);
		union(6, 9);
		union(9, 3);
		union(3, 8);
		union(0, 2);
		union(7, 0);
		union(3, 4);
		union(7, 6);
		union(5, 4);


		System.out.println(Arrays.toString(id));
		System.out.println(Arrays.toString(sz));

	}

	static int root(int i) {
		while (i != id[i]) {
			// 이줄만 추가해도 Tree를 압축할 수 있다!
			id[i] = id[id[i]];
			i = id[i];
			
		}

		return i;
	}

	static void initArray(int N) {
		id = new int[N];
		sz = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}

	static boolean checkConnected(int p, int q) {
		return root(p) == root(q);
	}

	static void union(int p, int q) {
		int i = root(p);
		int j = root(q);
		if (i == j) {
			return;
		}

		if (sz[i] < sz[j]) {
			id[i] = j;
			sz[j] += sz[i];
		} else {
			id[j] = i;
			sz[i] += sz[j];
		}

	}
}

[Java] Weighted Quick Union 알고리즘

Weighed Quick Union 알고리즘이다.
종전 Quick Find 알고리즘은 연결된 모든 노드의 ID를 죄다 같은 것으로 바꾸기 때문에 굉장히 시간이 오래 소요된다.(모든 Array Item을 다 뒤져야함)
하지만 이 알고리즘은, 연결된 Node의 ID를 다 바꾸는 것이 아니라, 각각의 Root 만 찾아서 그 Root 값으로만 바뀌기 때문에 logN(root탐색시간) 만큼만 걸린다.

import java.util.Arrays;
import java.util.Scanner;

public class Weighted_Quick_Union {

	private static int[] id;
	private static int[] sz;

	public static void main(String[] args) {

		initArray(10);

		union(1, 7);
		union(6, 9);
		union(9, 3);
		union(3, 8);
		union(0, 2);
		union(7, 0);
		union(3, 4);
		union(7, 6);
		union(5, 4);


		System.out.println(Arrays.toString(id));
		System.out.println(Arrays.toString(sz));

	}

	static int root(int i) {
		while (i != id[i]) {
			i = id[i];
		}

		return i;
	}

	static void initArray(int N) {
		id = new int[N];
		sz = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
			sz[i] = 1;
		}
	}

	static boolean checkConnected(int p, int q) {
		return root(p) == root(q);
	}

	static void union(int p, int q) {
		int i = root(p);
		int j = root(q);
		if (i == j) {
			return;
		}

		if (sz[i] < sz[j]) {
			id[i] = j;
			sz[j] += sz[i];
		} else {
			id[j] = i;
			sz[i] += sz[j];
		}

	}
}

[Java] Quick Find 알고리즘

가장 기초적인 Quick Find 알고리즘이다.
1~10번까지 node를 설정하고, 해당 노드들이 아래와 같은 조건으로 연결되어 있다고 가정할때 (union) 어떤 node끼리 최종적으로 연결되어 있는지 확인하는 알고리즘이다.

가장 기초적이 알고리즘이라고 할 수 있겠다.

import java.util.Arrays;

public class Quick_Find {

	private static int[] id;

	public static void main(String[] args) {
		
		
		initArray(10);
		
		union(4, 7);
		union(5, 9);
		union(6, 0);
		union(4, 3);
		union(6, 8);
		union(2, 5);
		
		System.out.println(Arrays.toString(id));

	}

	static void initArray(int N) {
		id = new int[N];
		for (int i = 0; i < N; i++) {
			id[i] = i;
		}
	}

	static boolean checkConnected(int p, int q) {
		return id[p] == id[q];
	}

	static void union(int p, int q) {
		int pid = id[p];
		int qid = id[q];

		for (int i = 0; i < id.length; i++) {
			if (id[i] == pid) {
				id[i] = qid;
			}
		}
	}
}