[2022 1학기] 11주차 - MST

1. MST란?

minimum spanning tree: 최소 신장 트리

-신장 트리(spanning tree): 무방향 그래프에서 모든 정점을 포함하는 트리

모든 정점을 포함하지만 사이클은 생성하면 안 된다

정점의 개수 n개, 간선의 개수 n-1개

-최소 신장 트리(minimum spanning tree): 사용된 간선의 가중치의 합이 최소가 되는 신장 트리

 

 

2. 동작 원리

-크루스칼 알고리즘

그래프의 모든 간선을 가중치의 오름차순으로 정렬한다

가중치가 낮은 간선부터 그래프에 삽입한다

사이클을 형성하는 간선은 삽입하지 않고 넘어간다

그래프에서 간선이 n-1개 삽입될 때까지 반복하고, n-1개가 된다면 멈춘다

 

-프림 알고리즘

그래프에서 시작 정점을 선택한다

선택한 정점에 부속된 모든 간선 중 가중치가 가장 낮은 간선을 연결해서 트리를 확장시킨다

사이클을 형성하는 간선은 삽입할 수 없으므로 다음으로 낮은 가중치의 간선을 선택한다

그래프에서 간선이 n-1개 삽입될 때까지 반복하고, n-1개가 된다면 멈춘다

 

3. 코드

//크루스칼 알고리즘
int kruskal() {
	int result = 0;

	priority_queue<pair<int, PII>> pq; //가중치, 정점1, 정점2

	for (int i = 1; i <= N; i++) {
		parent[i] = i;
	}

	for (int i = 0; i < M; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);

		pq.push({ -c, {a, b} });
	}

	while (!pq.empty()) {
		int u = Find(pq.top().second.first);
		int v = Find(pq.top().second.second);
		int cost = -pq.top().first;

		pq.pop();

		if (u == v) { //부모가 같다면 사이클이라서 continue
			continue;
		}
		else { //부모가 다르면 union
			Union(u, v);
			result += cost;
		}
	}
	return result;
}



//프림 알고리즘

 

 

※공부 중 작성한 내용이기에 틀린 부분이 있을 수도 있습니다!