Minimum Spanning Tree 알고리즘

대표 예제

풀이 방법이 2가지 있다. 

9개의 도시가 모두 연결되어야하는데 최소 비용으로 연결해야 한다. 

그래프 → 최소비용의 트리로 만들어야한다.

트리는 n개의 정점이 있으면 간선은 n-1개만 있으면 된다.

 

Kruskal MST

1. 우선 들어오는 간선들의 가중치를 기준으로 오름차순으로 나열한다.

 

2. 밑에서부터 선택한다. 

이 때 무조건 밑에서부터 선택하는 것은 아니고

만약에 간선을 선택했는데 회로가 되면 간선을 선택하면 안된다.

ex) 2 3 10이 들어 왔을 때 

2번과 3번이 이미 연결되어 있는지 find함수로 확인한다.

이 때 2번과 3번의 집합이 서로 다른 집합이면 연결한다.

빨간색으로 표시 된거는 트리의 원소가 된 것(union으로)

8 9 15 까지 했을 때의 모습

 

3. 만약 같은 집합이 나오면

2 8 17이 왔을 때

find(2)하고 find(8)하면 같은 집합으로 나올 것이다.

따라서 선택하면 회로가 되므로 안된다.

즉 둘은 이미 연결되있으므로 또 연결할 필요가 없다.

즉 최소 비용을 선택하라는 것은 회로를 피하라는 것

그래서 최종적으로 이렇게 된다. 

 

정리

Kruskal 알고리즘은 최소 비용 신장트리 만드는 과정에서

간선을 내림차순 하고 작은거 부터 선택

대신 회로가 발생하지 않도록 간선을 n-1개 선택한다.

 

코드

for(i=1; i<=m; i++){
	scanf("%d %d %d", &a, &b, &c);
	Ed.push_back(Edge(a,b,c));
}

for(i=1; i<=n; i++){
	unf[i]=1;
}
sort(Ed.begin(), Ed.end());
for(i=0; i<m; i++){
	int fa=Find(Ed[i].v1);
	int fb=Find(Ed[i].v2);
	if(fa!=fb){
		res+=Ed[i].val;
		Union(Ed[i].v1, Ed[i].v2);
	}
}
printf("%d\n",res);

 

Prim MST

Prim은 간선을 선택하는 것이 아니다.

임의의 정점을 하나 선택하고 그래프의 연결관계 보면서 정점을 하나씩 추가해나가는 방법.

☆정점을 추가

그렇게 정점이 n개가 되면 트리가 완성되는 것이다.

1. 임의의 출발 정점 1번을 잡겠다.

퍼져나가더라도 간선의 최소값으로 → 우선순위 큐 구조 사용

최초로 (1,0) 넣는다. 

큐에서 하나 꺼내면

1번 정점과 연결된 2개의 노드 큐에 넣는다. 

정점 번호하고 가중치를 넣는다. 

(2, 12) (9,25)

 

2. 그리고 pop한다. 2번 정점이 트리에 원소로 추가 된다.

→  이 간선이 선택됐다는 것이고  2번이 트리의 정점이 됐다.

큐에는 (9,25) 만 남는다.

그리고 2에서 갈수 있는 거 다 추가한다. (9,8), (8,17), (3,10)

 

3. 최소 힙이니까 제일 작은 (9,8)이 나온다. 

9번에서 뻗어나오는 것들을 다시 큐에 넣어야한다.

 

간선의 가중치 pop하더라도 이미 추가 된거라면 추가하면 안된다.

그래서 정점 번호를 chk배열로 체크 해야한다.

그리고 그 노드에서 뻗어나올 수 있는 간선들 pq에 push한다.

 

4. 그리고 최종적으로 큐가 비면 알고리즘이 끝난다.

int main(){
	freopen("input.txt", "rt", stdin);
	priority_queue<Edge> Q;
	vecctor<pair<int, int>> map[30];
	int i, n, m, a, b, c, res=0;
	scanf("%d %d", &n, &m);
	for(i=1; i<=m; i++){
		scanf("%d %d %d", &a, &b, &c);
		map[a].push_back(make_pair(b,c));
		map[b].push_back(make_pair(a,c));
	}
	Q.push(Edge(1,0));
	while(!Q.empty()){
		Edge tmp=Q.top();
		Q.pop();
		int v=tmp.e;
		int cost=tmp.val;
		if(ch[v]==0){
			res+=cost;
			ch[v]=1;
			for(i=0; i<map[v].size(); i++){
				Q.push(Edge(map[v][i].first, map[v][i].second));
			}
		}
	}
	printf("%d\n",res);
	return 0;
}

 

 

 

 

출처: it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++)