최소 신장 트리(MST)

MST(Minimum Spanning Tree)로 대표적으로 크루스칼 알고리즘, 프림 알고리즘 두가지가 있다.

1. 크루스칼 알고리즘(Kruskal Algorithm)

가장 적은 비용으로 모든 노드를 연결하기 위해 사용합니다. 그리디를 이용한 것으로 그 순간에 최적이라고 생각하는 것을 선택합니다.

로직

1. 가중치에 따라 내림차순 정렬
2. 가장 작은 간선 e를 뽑고
3. e를 신장트리에 넣었을 때 사이클이 생기면 중단하고 2번으로 이동
4. 사이클이 생기지 않으면 최소 신장트리에 삽입
5. n-1개의 간선을 넣을 때까지 반복합니다.

   • 간선 추가시 사이클 검사 과정 필요
     Union-Find 알고리즘
     여러개의 노드가 존재할 때 두개의 노드를 선택해서 이 두 노드가 같은 그래프에 속하는지 판별
     union : 두 집합의 합집합을 만드는 연산
     find : 원소가 속한 집합을 찾는 연산

---

int getParent(int x) {
	if (parent[x] == x)return x;
	return parent[x] = getParent(parent[x]);
}

부모가 누군지 찾는 함수입니다.
Union-find의 find과정입니다.

---

void unionParent(int a, int b) {
	a = getParent(a);
	b = getParent(b);
	if (a < b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

부모를 같게 만들어주며 최소 신장트리에 추가하는 함수입니다.
Union-find의 Union과정입니다.

---

2. 프림 알고리즘

크루스칼과 달리 정점 기준
1. 그래프에서 시작 정점을 선택하여 초기 트리를 만든다.
2. 현재 트리의 정점들과 인접한 정점들 중에서 간선의 가중치가 가장 작은 정점 v를 선택
3. 정점 v와 간선을 트리에 추가
4. 모든정점 삽입되면 종료