[알고리즘] 최소 스패닝 트리 : 크루스칼 (Kruskal)

크루스칼 (Kruskal)

• 가중치의 합이 가장 작은 트리를 찾는 최소 스패닝 트리를 푸는 알고리즘 중 하나
• 간선이 하나도 없는 상태에서 시작해 하나씩 트리에 간선을 추가해 가는 탐욕적 알고리즘
• 간선을 오름차순으로 정렬하고 이미 트리에 추가된 간선과 사이클을 이루지 않을 때 간선을 추가
• 간선이 사이클이 되지 않는지 확인하기 위해 유니온 파인드를 사용

동작 과정

1.

가중치가 오름차순으로 정렬된 우선순위 큐에 모든 간선을 추가한다.

우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치)

: (0,1,1), (1,3,1), (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5)

2.

poll 한 값의 두 노드의 부모가 같은지 판단(사이클 여부 확인)하여 같지 않다면 사이클을 이루지 않는다고 판단한다.

따라서 두 노드의 부모를 더 작은 값의 부모의 값으로 변경한다.

 

poll 한 값 : (0,1,1)

우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치)

: (1,3,1), (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5)

3.

2번과 동일

 

poll 한 값 : (1,3,1)

우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치)

: (2,3,2), (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5)

4.

2번과 동일

 

poll 한 값 : (2,3,2)

우선순위 큐 (노드1, 노드 2, 두 노드 사이의 가중치)

: (5,6,2), (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5)

5.

2번과 동일

 

poll 한 값 : (5,6,2)

우선순위 큐 (노드1, 노드 2, 두 노드 사이의 가중치)

: (1,5,3), (1,6,3), (3,6,3), (0,1,5), (3,4,5)

6.

2번과 동일

 

poll 한 값 : (1,5,3)

우선순위 큐 (노드1, 노드 2, 두 노드 사이의 가중치)

: (1,6,3), (3,6,3), (0,1,5), (3,4,5)

7.

2번과 달리 poll 한 값의 두 노드의 부모가 같은지 판단(사이클 여부 확인)하여 같기 때문에 사이클을 이룬다고 판단한다.

사이클을 이루기 때문에 해당 간선은 패스하게 된다.

 

poll 한 값 : (1,6,3)

우선순위 큐 (노드 1, 노드 2, 두 노드 사이의 가중치)

: (3,6,3), (0,1,5), (3,4,5)

 

poll 한 값 : (3,6,3)

우선순위 큐 (노드1, 노드 2, 두 노드 사이의 가중치)

: (0,1,5), (3,4,5)

 

poll 한 값 : (0,1,5)

우선순위 큐 (노드1, 노드 2, 두 노드 사이의 가중치)

: (3,4,5)

8.

2번과 동일

 

poll 한 값 : (3,4,5)

우선순위 큐 (노드1, 노드 2, 두 노드 사이의 가중치)

:

static int parent[] = new int[v+1]; // 부모 인덱스를 담는 배열
static int v; // 정점의 개수
static int e; // 간선의 개수

for(int i = 0; i < v+1; i++) { // 부모 인덱스 담는 배열 자기 자신 노드로 초기화 
	parent[i] = i;
}

static int find(int x) {
	if(x == parent[x]) {
		return x;
	}else {
		return parent[x] = find(parent[x]);
	}
}
	
static void union(int x, int y) {
	int xRoot = find(x);
	int yRoot = find(y);
		
	// 부모가 같지 않을때 더 작은값으로 넣어줌
	if(xRoot != yRoot) {
		if(x < y) parent[yRoot] = x;
		else parent[xRoot] = y;
	}
}

static void Kruskal() {
	while(!pq.isEmpty()) {
		edge cur = pq.poll();
			
		int a = find(cur.snode1);
		int b = find(cur.node2);
			
		if(a == b) { // 부모 인덱스가 같은 경우
			continue;
		}
		union(a,b);
		result += cur.weight;
			
	}
}


static class edge implements Comparable<edge>{
	int node1;
	int node2;
	int weight;
		
	edge(int node1, int node2, int weight) {
		this.node1 = node1;
		this.node2 = node2;
		this.weight = weight;
	}

	// 가중치를 오름차순으로 정렬
	@Override
	public int compareTo(edge o) {
		return weight - o.weight;
	}
}