최소 신장 트리 - Kruskal (Union Find)

 

 

 

신장 트리는 그래프에서 모든 노드가 연결되어 있고, 사이클이 없는 그래프를 의미한다.

최소 신장 트리는 신장 트리에서 가중치를 부여하고, 만들 수 있는 신장 트리 중 가중치의 합이 최소인 그래프를 의미한다.

 

그래프가 주어졌을 때 최소 신장 트리를 찾을 수 있는 알고리즘으로는 크루스칼과 프림 알고리즘이 있다.

 

먼저 크루스칼 알고리즘에 대해 알아보자.

 

 

Kruskal

 

 

그리디 알고리즘을 기반으로 해 최소 신장 트리를 구한다.

 

1. 그래프의 모든 노드들을 연결되지 않은 상태로 놓는다.

 

2. 존재하는 모든 간선들을 비용을 기준으로 정렬하고, 비용이 적은 간선부터 연결을 시작한다. (같은 비용이면 아무거나 선택해도 괜찮음)

 

3. 연결된 후 노드들의 최상위 노드를 확인 후 최상위 정점이 같으면 연결하지 않고 (사이클이 없어야 한다), 다르면 연결한다.

 

 

 

 

 

 

위 그림과 같은 과정으로 진행된다.

크루스칼 알고리즘에서 사이클이 있는지 판단하는 과정을 코드로 구현하기에는 복잡한데, 사이클 여부를 확인할 때는 Union Find 알고리즘을 사용한다.

 

 

 

Union Find

 

 

 

Union Find알고리즘은 한 집합에 대해 부분집합으로 분할할 때, 각각의 부분집합들이 Mutually Disjoint 상태를 유지하도록 분할하는 알고리즘이다.

 

노드들 중에서 서로 연결된 노드를 찾거나, 노드들을 연결할 때 사용할 수 있고, 크루스칼 알고리즘에서는 노드들이 사이클을 가지는지 확인할 때 사용된다.

 

트리 구조를 사용해 각각의 집합을 트리 구조로 관리하고, 두 개의 집합을 하나의 집합으로 합칠 때 두 트리를 하나의 트리로 만든다.

 

 

 

첫 번째 트리와 두 번째 트리를 간선으로 연결한다고 생각해보자.

각각의 트리의 루트 노드가 서로 다르기에 사이클이 없음을 알 수 있고, 오른쪽 그림과 같이 합쳐진다.

 

만약 A와B를 합친다고 하면 각 트리의 루트 노드가 같기 때문에 사이클을 방지하기 위해 합치지 않는다.

 

 

트리를 합칠 때도 주의해야 한다.

 

아무런 기준 없이 합치게 되면 계속해서 트리의 레벨이 늘어나게 될 수 있고, 이 경우 트리 구조를 효과적으로 사용하지 못한다.

 

union-by-rank

 

 

트리를 합칠 때 각각의 레벨을 기억해 두고, 레벨이 다른 트리를 합칠 때는 레벨이 작은 트리를 레벨이 큰 트리에 붙이는 방식으로 트리를 합치고, 같은 레벨의 트리를 합치는 경우는 둘 중 하나의 레벨을 증가시키고 합친다.

 

 

시간복잡도 O(n) -> O(logn)

 

 

path compression

 

 

비효율적으로 구성된 트리를 압축하는 기법이다.

트리에 대해 루트 노드를 확인할 때 루트 노드의 자식으로 노드들을 추가하는 방식이다.

 

 

 

이 두 가지 기법을 사용해 Union Find의 시간복잡도를 크게 낮출 수 있다.

 

 

 

크루스칼 알고리즘을 구현해보자.

 

 

public class Edge implements Comparable<Edge> {
	public int weight; // 가중치
	public String nodeV; // 간선과 연결된 노드
	public String nodeU; // 간선과 연결된 노드
	
	public Edge(int weight, String nodeV, String nodeU) {
			this.weight = weight;
			this.nodeV = nodeV;
			this.nodeU = nodeU;
	}
	
	@Override 
	public int compareTo(Edge edge) { // 비교할 수 있도록 compareTo메서드 정의
			return this.weight - edge.weight;
	}
}

 

 

 

public class KruskalPath {
	HashMap<String, String> parent = new HashMap<String, String>(); // <Union Find> 부모 노드를 저장 
	HashMap<String, Integer> rank = new HashMap<String, Integer>(); // <Union Find> 각 노드별로 레벨을 저장
	
	public String find(String node) { 
			// path compresion 기법 사용
			if (this.parent.get(node) != node) { // 부모 노드가 루트 노드가 아니면 
					this.parent.put(node, this.find(this.parent.get(node))); // 부모 노드의 부모 노드를 찾고, 트리 압축
			}
			return this.parent.get(node); // 부모 노드가 루트 노드이면 반환해준다.
	}
	
	public void union(String nodeV, String nodeU) { // 
			String root1 = this.find(nodeV);
			String root2 = this.find(nodeU);
			
			// union-by-rank 기법 사용
			if (this.rank.get(root1) > this.rank.get(root2)) { // 레벨이 다르면 레벨이 큰 쪽이 흡수함
					this.parent.put(root2, root1);
			} else {
					this.parent.put(root1, root2);
					if (this.rank.get(root1) == this.rank.get(root2)) {
							this.rank.put(root2, this.rank.get(root2) + 1); // 레벨이 같으면 둘 중 하나의 레벨을 증가시키고 흡수
					}
			}
	}
	
	public void makeSet(String node) { // 초기 상황은 노드가 하나인 트리이다.
			this.parent.put(node, node); // 부모 노드를 자기 자신으로 설정.
			this.rank.put(node, 0); // 레벨도 0으로 설정.
	}
	
	public ArrayList<Edge> kruskalFunc(ArrayList<String> vertices, ArrayList<Edge> edges) {
		// 그래프 정보를 입력받는다.
			ArrayList<Edge> mst = new ArrayList<Edge>(); // 정답을 저장하는 리스트
			Edge currentEdge; 
			
			// 1. 초기화
			for (int index = 0; index < vertices.size(); index++) {
					this.makeSet(vertices.get(index));
			}
			
			// 2. 간선 weight 기반 sorting
			Collections.sort(edges);
			
			for (int index = 0; index < edges.size(); index++) {
					currentEdge = edges.get(index);
					if (this.find(currentEdge.nodeV) != this.find(currentEdge.nodeU)) { // Union Find - find
							this.union(currentEdge.nodeV, currentEdge.nodeU); // Union Find - Union
							mst.add(currentEdge);
					}
			}
			
			return mst;
	}
}

 

 

 

시간복잡도 : 초기화 + 정렬 + 합치기 O(V) + O(E logE) + O(E) (Union Find) => O(E log E)

V = vertex(node) E = edge(간선)