[알고리즘] 최소신장트리(Minimum Spanning Tree) 복습 겸 정리

♟️ 최소 신장 트리(Minimum Spanning Tree)?

최소 신장 트리는 주어진 그래프의 모든 정점을 포함하는 부분 그래프를 의미한다.

부분 그래프는 주어진 그래프에서 일부 정점과 간선만을 선택해 구성한 새로운 그래프를 의미한다.

신장 트리는 주어진 그래프의 정점이 V개일 때 V-1개의 간선을 가지고 있다.

최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 말한다.

최소 신장 트리를 구하는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다.

크루스칼(kruskal) vs 프림(prim)

 

크루스칼은 현재 선택할 수 있는 정점 중 가중치가 가장 적은 간선을 선택하여 모든 정점이 연결될 때 까지 연결

 

프림은 임의의 한 정점과 연결된 정점들에 대해, 가장 가중치가 작은 간선을 연결하면서 트리 집합을 단계적으로 확장

♟️ 크루스칼 알고리즘(Kruskal)

크루스칼 알고리즘은 유니온 파인드(Union-Find) 알고리즘을 알아야 효율적으로 구현할 수 있다.

크루스칼 알고리즘은 간선의 비용 순으로 살펴보며 서로 떨어진 정점들을 선택해 총 V-1개의 간선을 선택하는 알고리즘이다.

크루스칼 알고리즘 과정

1. 간선을 오름차순으로 나열 후 가장 가중치가 작은 임의의 간선을 하나 택한다.
2. 해당 간선으로 연결된 두 정점을 하나의 그룹으로 묶는다.
3. 다음으로 가중치가 작은 임의의 간선을 하나 택한다.
4. 선택한 간선으로 연결된 두 정점의 그룹이 다르다면 그룹을 묶고, 같으면 무시한다.
5. 정점의 개수가 V개 일 때, 선택한 간선의 개수가 V-1개이면 종료한다.

크루스칼 구현 방법

1. 간선을 리스트에 담아서 비용을 기준으로 오름차순 정렬한다. (우선순위 큐도 가능!!)
2. 반복문을 간선의 수만큼 진행하며, 선택한 간선 수가 N-1개이면 종료한다.
3. 리스트에서 간선을 꺼내어, 두 정점이 같은 그룹에 속하는지 확인한다.
   • 유니온 파인드(Union-Find)로 확인했을 때, 다른 그룹이면 하나의 그룹으로 묶는다.
   • Union By Rank, 경로 압축 최적화도 진행한다.
4. 같은 그룹이면 다음 반복문으로 넘어간다.
5. 다른 그룹이면 해당 간선을 선택하고, 비용과 선택한 간선 수를 업데이트 한다.

static int N, M, tree[]; // N:정점 수, M:간선 수, tree[]:부모의 정점을 저장할 배열
static ArrayList<int[]> list = new ArrayList<>();

public static void main(String[] args) {
	for(int i=0; i<M; i++){
		list.add(new int[]{cost, u, v});
	}
	Collections.sort(list, (a,b)->(a[0]-b[0]));
	int cost = 0, edge = 0; // cost:최소비용, edge:선택한 간선 수
	
	// 간선 수만큼 반복
	for(int i=0; i<M; i++){
		int[] current = list.get(i);
		if(!union(current[1], current[2])) continue; // 이미 같은 그룹이면 무시
		cost += current[0]; // 비용 추가
		edge++; // 간선 수 증가
		if(edge==N-1) break;
	}
}

public static boolean union(int u, int v){
	int a = find(u);
	int b = find(v);
	if(a==b) return false; // 이미 같은 그룹
	tree[b] = a; // 그룹으로 묶기
	return true;	
}

public static int find(int x){
	if(tree[x]<0) return x;
	return tree[x] = find(tree[x]); // 경로 압축 최적화
}

---

♟️ 프림 알고리즘(Prim)

프림 알고리즘은 우선순위 큐만 사용해서 구현할 수 있다.

프림 알고리즘은 임의의 한 정점에서 시작하여 매번 인접한 간선들 중 비용이 가장 적은 간선을 선택하여 정점들을 하나씩 연결시키며 총 V-1개의 간선을 선택하는 알고리즘이다.

그리고 이미 선택한 정점에 대해 다시 간선을 추가하지 않기 때문에 싸이클이 생길 수 없다.

프림 알고리즘 과정

1. 임의의 한 정점을 선택 후 연결된 간선들 중 가장 비용이 적은 간선을 하나 택한다.
2. 해당 간선으로 연결된 정점을 최소신장트리에 추가한다.
3. 최소신장트리에 포함된 정점들과 최소신장트리에 포함되지 않은 정점들을 연결하는 간선 중 가중치가 가장 작은 것을 선택하여 최소신장 트리에 추가한다.
4. 정점의 개수가 V개 일 때, 선택한 간선의 개수가 V-1개이면 종료한다.

프림 구현 방법

매번 최소 신장 트리에 포함된 정점들과 포함되지 않은 정점들을 확인하고, 그 중 가장 작은 간선을 선택하면 시간복잡도가 O(VE)로 매우 비효율적임. 그러므로 우선순위 큐를 활용한다.

1. 최소신장트리에 포함됐는지 확인하기 위해 정점들의 방문배열을 생성한다.
2. 임의의 정점을 선택해 비용을 기준으로 오름차순으로 정렬하는 우선순위 큐에 {정점, 비용}형태의 배열로 추가한다.
3. 우선순위 큐에서 정점을 하나 꺼내어 해당 정점을 방문했으면 무시하고 넘어간다.
4. 해당 정점을 방문하지 않았으면, 방문처리하고 선택한 간선 수를 증가시킨다.
5. 해당 정점과 연결된 정점들 중 방문하지 않은 정점과 연결된 간선들을 큐에 넣는다.
6. 정점의 개수가 V개 일 때, 선택한 간선의 개수가 V-1개이면 종료한다.

static int N, M;
static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
static boolean[] visit;

public static void main(String[] args) {
	visit = new boolean[N+1];
	for(int i=0; i<M; i++){
		list.get(u).add(new int[]{v,cost});
		list.get(v).add(new int[]{u,cost});
	}
	int ans = prim(); // 최소 비용
}

public static int prim(){
	int cost = 0, edge = 0; // cost:최소비용, edge:선택한 간선 수
	PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->(a[1]-b[1]));
  	q.add(new int[]{1,0}); // 임의의 한 정점부터 시작
  
  	while(!q.isEmpty()){
	  	int[] current = q.poll();
	  	int curNode = current[0];
    	int curCost = current[1];
    	if(visit[curNode]) continue; // 방문했으면 다음 반복문으로
    	visit[curNode] = true; // 방문처리
    	edge++;
    	cost += curCost;
    
    	for(int[] next : list.get(curNode)){
        	int nextNode = next[0];
        	int nextCost = next[1];
        	if(!visit[nextNode]){
            q.add(new int[]{nextNode, nextCost});
        	}
    	}
    	if(edge==N) break; // 처음 시작점에 하나더 카운트해줘서 N-1개가 아니라 N개
  	}// while
  	return cost;
}// prim

참고자료

BaaaaaaaarkingDog : [실전 알고리즘] 0x1B강 - 최소 신장 트리