알고스팟(algospot) 31장 최소 스패닝 트리(크루스칼과 프림 알고리즘)

31.1 도입

-스패닝 트리(=신장 트리)?  --> 사이클이 없고, 그래프 내의 모든 정점을 포함하는 트리

     -일반 스패닝 트리는 여러 개가 있을 수 있다.

     -최소 스패닝 트리는 무조건 1개!

 

- 최소 스패닝 트리를 해결해줄 2가지 알고리즘!

   크루스 칼 알고리즘--> 배타적 집합 자료구조의 사용! (Union find)

   프림 알고리즘--> 다익스트라 알고리즘과 비슷

    * 둘 다 무방향 그래프일 때만 사용!

 

 

31.2 크루스 칼의 최소 스패닝 트리 알고리즘

 

가중치가 작은 간선과 큰 간선중 어느 쪽이 최소 스패닝 트리에 포함될 가능성이 높을까?---> 당연히 작은 간선!

 

이를 통한 알고리즘!

1. 모든 간선을 가중치의 오름 차순으로 정렬한 뒤

2. 하나씩 추가해감

3. 사이클이 생기는 간선은 바로 제외(Union find로 판별)

 

이렇게 모든 간선을 한 번씩 검사하고 난 뒤에 종료

// Algorithm Analysis
// 크루스칼 알고리즘 (Kruskal Algorithm)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 속한 집합 찾기
int getSet(int set[], int x) {
	if (set[x] == x) return x;
	return set[x] = getSet(set, set[x]);
}

// 두 집합 합치기
void unionSet(int set[], int a, int b) {
	a = getSet(set, a);
	b = getSet(set, b);
	if (a < b)
		set[b] = a;
	else
		set[a] = b;
}

// 동일한 집합 내에 속해있는지 확인
int find(int set[], int a, int b) {
	a = getSet(set, a);
	b = getSet(set, b);
	if (a == b) return 1;
	return 0;
}

// 간선 정보 클래스
class Edge {
public:
	int vtx[2]; // 연결된 2개의 정점
	int distance; // 거리(비용)
	Edge(int a, int b, int distance) {
		this->vtx[0] = a;
		this->vtx[1] = b;
		this->distance = distance;
	}
	bool operator <(Edge& edge) {
		return this->distance < edge.distance; // 적은 거리 우선 정렬
	}
};
int main() {
	int v = 9; // 정점 수 (0~8)

	vector<Edge> data; // 간선 데이터 배열
	data.push_back(Edge(0, 1, 8)); // 정점0과 정점1의 간선 비용8
	data.push_back(Edge(0, 2, 12));
	data.push_back(Edge(1, 2, 13));
	data.push_back(Edge(1, 3, 25));
	data.push_back(Edge(1, 4, 9));
	data.push_back(Edge(2, 3, 14));
	data.push_back(Edge(2, 6, 21));
	data.push_back(Edge(3, 4, 20));
	data.push_back(Edge(3, 5, 8));
	data.push_back(Edge(3, 6, 12));
	data.push_back(Edge(3, 7, 12));
	data.push_back(Edge(3, 8, 16));
	data.push_back(Edge(4, 5, 19));
	data.push_back(Edge(5, 7, 11));
	data.push_back(Edge(6, 8, 11));
	data.push_back(Edge(7, 8, 9));

	// 간선 비용을 기준으로 정렬
	sort(data.begin(), data.end());

	int set[9];
	for (int i = 0; i < v; i++) {
		set[i] = i;
	}
	int sum = 0; // 최소 비용 합

	for (int i = 0; i < data.size(); i++) {
		// 사이클이 발생하지 않으면 그래프에 포함
		if (!find(set, data[i].vtx[0], data[i].vtx[1])) {
			sum += data[i].distance;
			unionSet(set, data[i].vtx[0], data[i].vtx[1]);
		}
	}
	cout << sum;
}

 

 

 

31.3 프림의 최소 스패닝 트리 알고리증

인접 간선만을 고려한다는 점만 빼면 

가중치가 작은 간선만 선택한다는 크루스 칼 알고리즘과 비슷!

 

여기서... 단순히 간선을 찾고 하나 추가한다면 시간 복잡도 upup

---> 최적화 필요..!

---> 현재 스패닝 트리에 이미 존재하는 정점은 탐색 X

 

const int MAX_V = 100;
const int INF = 987654321;
 
int V=6;
 
vector<pair<int, int> > adj[MAX_V];
 
int prim(vector<pair<int, int> > &selected) {
    selected.clear();
 
    vector<bool> added(V, false);
    vector<int> minWeight(V, INF), parent(V, -1);
 
    int ret = 0;
    minWeight[0] = parent[0] = 0;
    for (int iter = 0; iter < V; iter++) {
        int u = -1;
        for (int v = 0; v < V; v++) {
            if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
                u = v;
        }
 
        if (parent[u] != u)
            selected.push_back(make_pair(parent[u], u));
 
        ret += minWeight[u];
        added[u] = true;
 
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i].first, weight = adj[u][i].second;
            if (!added[v] && minWeight[v]>weight) {
                parent[v] = u;
                minWeight[v] = weight;
            }
        }
    }
    return ret;
}

다익스트라 알고리즘과 매우 비슷

 

 

 

 

---

문제들

31.4 근거리 네트워크

31.6 여행경로 정하기