1.最小長ツリー

伸長木:所与の接続図からループを形成する幹線を削除して作成する木

.

最小伸長木:幹線重み付け最小伸長木

の各都市が頂点であり、道路が幹線であり、都市間の距離が重み付け値である場合、最小伸長木はすべての都市間に自転車が接続されていないことを意味するが、距離の和は最小の道路網である.

頂点の個数がnである場合、全頂点を無周期に接続し、幹線の個数は常に(n−1)個である.

最小伸長木を求める代表的な方法はクルースカ、プリムアルゴリズムがある.

クルースカアルゴリズムは重み付けが最小の幹線から始まり、primアルゴリズムは重み付けが最小の頂点から始まり、MSTに1つずつ含まれるので、どちらもgreedyアルゴリズムとすることができる.

2.クルーズアルゴリズム

https://www.youtube.com/watch?v=LQ3JHknGy8c
https://blog.naver.com/ndb796/221230994142

アルゴリズムの理解

まず、昇順に幹線の重み付けを並べます.

の重み付け値が幹線から周期を形成しているかどうかを確認します.(Union-Find:2つのノードが同じセットにあるかどうかを確認)

サイクルを形成しない幹線のみを含む.

Union findアルゴリズムとは何か、以下の記事を参照してください.
https://velog.io/@jxlhe 46/アルゴリズム-Union-Find-Union-Find

コードで実現

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 각 정점의 부모 노드 번호를 저장하는 배열 (최종적으로는 루트 노드 번호)
int parent[10'000];

// 루트 노드를 찾는 Find 연산
int Find(int x) {
	// 배열의 인덱스와 값이 같다면 루트 노드 발견!
	if (x == parent[x]) return x;

	// 부모 노드의 번호를 전달하면서, 루트 노드를 찾을 때까지 재귀 호출 반복
	return parent[x] = Find(parent[x]);
}

// 두 노드를 같은 집합으로 합치는 Union 연산
void Union(int x, int y) {
	x = Find(x);
	y = Find(y);

	// 루트 노드가 같다면 이미 연결되어 있는 것
	if (x == y) return;

	// 더 작은 값이 부모 노드가 될 수 있도록
	if (x < y) parent[y] = x;
	else parent[x] = y;
}

// 두 노드가 연결되어 있는지 판별하는 함수
bool isUnion(int x, int y) {
	x = Find(x);
	y = Find(y);

	// 루트 노드가 같은지 확인
	return (x == y);
}

// 하나의 간선 정보를 담는 클래스
class Edge {
public:
	int node[2];
	int weight;

	Edge(int x, int y, int w) {
		this->node[0] = x;
		this->node[1] = y;
		this->weight = w;
	}

	// 가중치가 작은 간선부터 MST에 추가하도록
	bool operator < (Edge& edge) {
		return this->weight < edge.weight;
	}
};

int main() {
	int V; // 정점 개수
	scanf("%d", &V);

	int E; // 간선 개수
	scanf("%d", &E);

	int x, y, w; // 하나의 간선을 이루는 두 정점의 번호와 가중치
	vector<Edge> v;

	for (int i = 0; i < E; i++){
		scanf("%d %d %d", &x, &y, &w);
		v.push_back(Edge(x, y, w)); // 객체 배열 생성
	}

	// 간선의 가중치를 기준으로 오름차순 정렬
	sort(v.begin(), v.end());

	// 각 정점의 번호 초기화
	for (int i = 0; i < V; i++){
		parent[i] = i;
	}

	int sum = 0;
	for (int i = 0; i < v.size(); i++){
		// 사이클이 발생하지 않을 때만 MST에 추가
		if (!isUnion(v[i].node[0], v[i].node[1])) {
			sum += v[i].weight;
			Union(v[i].node[0], v[i].node[1]);
		}
	}

	printf("%d\n", sum);

	return 0;
}

じかんふくごうどぶんせき

出典:楊成峰、分かりやすいアルゴリズム、生エネルギー出版社、p.116

3.Primアルゴリズム

ぎじふごう

입력: 가중치 그래프 G=(V, E), |V|=n (정점 개수), |E|=m (간선 개수)
출력: 최소 신장 트리

1. 그래프 G에서 임의의 점 p를 시작점으로 선택, D[p]=0
// D[v]: T에 있는 점 u와 그 밖에 있는 점 v를 연결하는 간선 중에서 최소 가중치를 저장하는 배열
2. for(점 p가 아닌 각 점 v에 대해서){
3. 	if(그래프 상에 간선 (p, v)가 있으면)
4.		D[v] = 간선 (p, v)의 가중치
5.	else
6. 		D[v] = ∞
   }
7. T = {p} // 임의의 점 p부터 시작
8. while(T에 있는 점의 수 < n) {
9.  	T에 속하지 않은 각 점 v에 대해서, D[v]가 최소인 점 v_min을 찾아 T에 추가
10. 	for(T에 속하지 않은 각 점 w에 대해서) {
11. 		if(간선 (v_min, w)의 가중치 < D[w])
12. 			D[w] = 간선 (v_min, w)의 가중치 // D[w] 갱신
	}
    }
13. return T // 최소 신장 트리 T 리턴

アルゴリズムの理解

じかんふくごうどぶんせき

8. while(T에 있는 점의 수 < n) {
9.  	T에 속하지 않은 각 점 v에 대해서, D[v]가 최소인 점 v_min을 찾아 T에 추가
10. 	for(T에 속하지 않은 각 점 w에 대해서) {
11. 		if(간선 (v_min, w)의 가중치 < D[w])
12. 			D[w] = 간선 (v_min, w)의 가중치 // D[w] 갱신
	}
    }

n個のノードが共有され,D[v]配列で重み付けが最も小さい点v minを線形ルックアップとして探すたびに,時間複雑度はO(n^2)である.
最短パスアルゴリズムと同様に,配列ではなく最小スタックデータ構造を用いて現在のノードから最小のv minを検索することで,時間複雑度をO(logV)に低減できる.
注意:https://www.weeklyps.com/entry/%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-algorithm

4.クルーズvs.プリムアルゴリズム

クルーズアルゴリズムは,幹線の重み値を昇順に並べた後,周期を形成しない幹線のみをMSTに順次追加する.逆にprimアルゴリズムはMSTに属さない頂点に重み付けの最小の頂点を追加した.
すなわち、クルーズアルゴリズムが周期なしに「幹線」を次々と追加する場合、primアルゴリズムはMSTに属さない「頂点」を次々と追加する.
別の角度から見ると、クルーズはn本の木が次第に1本の木に合併し、フリームは1本の木で、最終的に1本の木になったと考えている.

白俊1197号です。

https://www.acmicpc.net/problem/1197