최소 스패닝 트리 (c++)

1. 최소 스패닝 트리의 정의

그래프 내의 모든 정점을 포함하는 그래프중에 사이클이 없는 그래프를 스패닝 트리라 하고

이중에 가장 가중치의 합이 적은(짧은 이라고 생각하자) 그래프를 최소 스패닝 트리라고 한다

 

2. 최소 스패닝 트리에서 알고리즘을 생각해보기

답만 아는것 보다는, 어떻게 그런 알고리즘이 나왔는지 떠올려보는게 기억하기에 좋다.

 

1. 일단 전체 간선중에 짧은 놈 순서대로 해보자(그리디 처럼)

2. 그런데 그 간선이 사이클을 만드는것만 체크하면 되겠네.

3. 같은 그룹인지만 확인할 수 있게하고, 같은 그룹 연결하지 않는 것  중에서 가장 짧은 순서대로 하면 됨.

4. 다 연결될때까지 or 정점개수가 n개라 할때 n-1개 간선을 선택할때까지 진행

 

이게 크루스칼 알고리즘이다. 

 

1. 일단 한놈 잡고, 얘하고 연결된 간선중에 가장 짧은 놈 고르자.

2. 그럼 연결된 정점이 있고, 이 2개의 정점중에 연결된 간선중 가장 짧은 놈 고르면 되겠네

3. 이거 계속 반복하면 되겠네, 같은 그룹인지만 계속 확인하면서

4. 다 연결될때까지 or 정점 개수가 n개라 할때 n-1개 간선을 선택할때까지 진행

 

이게 프림 알고리즘이다.

 

3. 최소 스패닝 트리 구현 

 

우선 아래 코드는 백준 1197번 최소 스패닝 트리 문제의 풀이에 대한 코드들이다.

 

3-1. 크루스칼 알고리즘

크루스칼 알고리즘에서 필요한 기법들과 이유

1. 우선 간선이 출발지와 도착지(양방향이므로 순서는 무관) 그리고 가중치가 있으니, 그것에 대한 구조체가 필요

2. 가장 짧은 놈을 찾기위한 구조체 정렬 필요(sort 사용)

3. 같은 그룹인지 확인할 방법 필요

 

1번 2번은 간단한 편이니 넘어가고 3번이 복잡한데

 

그냥 배열에 숫자 적어서 같은 숫자면 같은 그룹으로 하자. -> 2개의 그룹을 합칠때 한쪽 그룹 전부 바꿔아함 (시간초과)

 

따라서 트리 구조를 이용하여, 간선의 출발지 node와 도착지 node의 root가 같은지 다른지로 확인하게 된다. 

그러나 트리를 합칠때 그냥 대충 합친다 -> 트리의 높이가 너무 높아져서 root 찾는데 정점수만큼 걸림(시간초과)

 

트리를 합칠때에도 높이가 더 높아지지 않게 합쳐야 한다. 

 

아래 코드는 그 내용을 진행한 코드이다. 

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
struct line{ //간선 구조체 
	int start; //출발지(도착지)
	int end;  //도착지(출발지)
	int value; //가중치 
};
int node[10005]; //음수값, 0을 가지면 그것은 루트라는 뜻. 
//양수: 다른 노드를 가리킴, 음수값 or 0 이 트리의 높이를 의미 (0이면 자식이 없는 하나짜리)
line line_array[100005]; //간선들을 보유하는 배열 
line line_value;
int v,e;
int total_value; //가중치의 합

bool cmp(line a, line b){ //sort를 위한 정렬용 cmp(작은순)
	return a.value<b.value;
}
int find_root(int node_num){ //그 그룹을 이루는 트리의 root를 찾는 함수. 
	if(node[node_num]<=0)
		return node_num;
	else
		return find_root(node[node_num]);
}

int main() {
	scanf("%d %d",&v,&e);
	for(int i=0;i<e;i++){ //그냥 입력
		scanf("%d %d %d",&line_value.start,&line_value.end,&line_value.value);
		line_array[i]=line_value;
	}
	sort(line_array,line_array+e,cmp); //간선 정렬 
	for(int j=0;j<e;j++){
		line_value =line_array[j];
		if(find_root(line_value.start)!=find_root(line_value.end)){ //다른 그룹일때
			total_value+=line_value.value;
			int first_group=find_root(line_value.start);
			int second_group=find_root(line_value.end);
			if(node[first_group]>node[second_group]){ //첫 그룹이 숫자가 크다= 더작은 그룹이다
					int height=node[first_group]-1;
					node[first_group]=second_group;
					if(height<node[second_group])
						node[second_group]=height;
			}
			else{ //2번째 그룹이 더 작거나 같은 높이 그룹이다
				int height=node[second_group]-1;
				node[second_group]=first_group;
				if(height<node[first_group])
					node[first_group]=height;
			}
		}
	}
	printf("%d",total_value);
	
	return 0;
}

 

3-2. 프림 알고리즘

프림 알고리즘에서 필요한 기법들과 이유

1. 우선 간선이 출발지와 도착지(양방향이므로 순서는 무관) 그리고 가중치가 있으니, 그것에 대한 구조체가 필요

2. 가장 짧은 놈을 찾기위한 구조체 우선순위 queue 사용 필요 (정렬로 못하는게, 간선이 계속 추가되기 때문)

3. 같은 그룹인지 확인할 방법 필요

 

프림 알고리즘은 1,3번이 간단한 편이고 대신 2번이 복잡한 편

 

저번과 달리 그냥 그룹이 1개뿐이기 때문에, 같은 그룹인지 확인은 배열로 할 수 있지만

시작점으로 통하는 간선중에 가장 짧은 걸 선택해야하고, 이 가능한 간선이 계속 추가되기 때문에 

정렬대신 우선순위 queue를 사용해야만 함. (심지어 구조체에 대한 우선순위 queue를 사용해야함) 

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct line{ //간선 구조체
	int start; //출발지
	int end; //도착지
	int value; //가중치
};
struct compare{ //우선순위 queue를 위한 정렬(낮은거 먼저)
    bool operator()(line a, line b){
        return a.value>b.value;
    }
};
int n,m;
int a,b,c;
int answer;
line new_line,shortest;
int house[100001]; //집 index(같은 그룹인가?)
vector<line> line_info[100000]; //벡터의 배열 (각 집마다 가지고 있는 길)
priority_queue<line, vector<line>, compare> pq; //현재 확인해야할 길 

void put_lines(int house_num){ //우선순위 queue에 간선 투입 
	int vector_size=line_info[house_num].size();
	for(int i=0;i<vector_size;i++){
		pq.push(line_info[house_num][i]);
	}
}
int main() {
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&a,&b,&c);
		new_line.start=a;
		new_line.end=b;
		new_line.value=c;
		line_info[a].push_back(new_line);
		line_info[b].push_back(new_line);
	}
	house[1]=1; //1번 정점을 시작점으로 잡음. 
	put_lines(1);
	while(pq.size()!=0){ //우선순위 queue에서 떨어질때까지 
		shortest = pq.top();
		pq.pop();
		if(house[shortest.start]==1&&house[shortest.end]==1) //이미 연결된 정점끼리의 간선
			continue;
		else if(house[shortest.start]==1){
			house[shortest.end]=1;
			answer+=shortest.value;
			put_lines(shortest.end);
		}
		else{
			house[shortest.start]=1;
			answer+=shortest.value;
			put_lines(shortest.start);
		}
	}
	printf("%d",answer);
	return 0;
}

4. 최소 스패닝 트리의 생각할점, 주의할 점 등.

1. 일반적으로 음수 가중치의 간선이 있어도 상관이 없으나, 음수 가중치로만 이루어진 사이클이 있을경우 문제가 발생 

(크루스칼 알고리즘, 프림 알고리즘이 동작하기는 하나, 최소 스패닝트리를 만들었다고 합이 최소가 아닐 수 있음)

2. 간선이 많을 경우 프림 알고리즘이, 간선이 적을수록 크루스칼 알고리즘이 유리함. 다만, 프림이 일반적으로는 더 빠름.

3. 일반적으로 모든 정점(집, 회사, 컴퓨터)이 하나로 가장 적은 가중치로(짧게, 싸게) 연결되어야 하면 최소 스패닝 트리임.

 

긴 글 읽어주셔서 감사합니다

실례가 되지않는다면 광고 한번씩만 클릭해 주시면 큰 힘이 됩니다.

댓글도 하나씩 달아주시면 정말 감사하겠습니다.