> 補充教材: [Graph / 圖](/JRiwv0omQ9e7JGynHgYeuQ)

## 何謂生成樹

在一張圖中，選一些邊使圖連通
如果這個子圖是一棵樹，那它就是Spanning Tree(生成樹)

e.g.


這是一張圖


如果我們選一些邊


像這樣，是一棵樹，則這一顆就是生成樹

---

## 何謂最小生成樹

一張邊上帶權重的圖，取一些邊使其為一生成樹且邊權總和最小

先看一張帶權重的圖

這張圖的其中一個最小生成樹如下

一張圖可能不只有一個最小生成樹，以下這也是一個最小生成樹

---

## 如何求最小生成樹

### Kruskal's algorithm

#### 概念

最直覺的演算法，對所有邊依照權重由小到大排序
當一個邊兩側的點不連通，就連起來並加進MST

i.e.

一開始每個點都是一個集合

找最小的邊，而邊的兩端點不在相同集合則合併

同上，合併

同上

接下來，遇到該邊的兩端點在相同集合，則跳過

繼續找最小邊合併

最後會把所有邊遍歷完，用實線連起來的邊即為MST

想法很簡單，但需要一個可以快速實現判斷連通與否的資料結構

> [Disjoint Set Union (DSU) / 互斥集](/ktXqlbtaSpGoxGH6MNef-w)

有了這個資料結構，接下來的實作就很簡單了

#### 範例程式碼

inline void solve() {
//caculate MST weight sum
	int n,m;
	while(cin>>n>>m){
		vector<edge> e(m,edge(0,0,0));
		for(auto& i:e){
			int a,b,w;
			cin>>a>>b>>w;
			i=edge(a,b,w);
		}
		sort(e.begin(),e.end());
		vector<int> dsu(n);
		iota(dsu.begin(),dsu.end(),0);
		F<int(int)> find=[&](int x){
			return x==dsu[x]?x:dsu[x]=find(dsu[x]);
		};
		auto join=[&](int a,int b){
			if(find(a)==find(b))
				return false;
			dsu[find(a)]=dsu[find(b)];
			return true;
		};
		long long sum=0;
		for(const auto& i:e)
			if(join(i.a,i.b))
				sum+=i.w;
		int isconnected=true;
		for(int i=0;i!=n;i++)
			if(find(0)!=find(i))
				isconnected=false;
		cout<<(isconnected?sum:-1)<<endl;	
	}
}

---

### Prim's algorithm

#### 概念
和 [Kruskal's algorithm](#Kruskal’s-algorithm) 不一樣的是 [Prim's algorithm](#Prim's-algorithm) 是由點的想法出發
先任意找一個點，從該點延伸出的邊中取權重最小者，再從該點延伸重複做以上操作，可以使用 `priority_queue` 維護並快速取出邊權最小者，直到連接中的點皆已被拜訪為止，最後判斷點的數量是否為邊的數量加一。

i.e.

一開始先指定任一點當起始點

延伸出去，將出邊放進`priority_queue`，並取最小者

繼續延伸，選最小邊

同上

同上，所有點遍歷完成

#### 範例程式碼 (GT)

vector<pii> g[N];
vector<bool> v;
ll prim(int n, int m) { // n vertices, m edges
	v.assign(n, 0);
	for (int i = 0; i < n; g[i].clear(), i++);
	for (int i = 0, a, b, c; i < m; i++)
		cin >> a >> b >> c, g[a].eb(b, c), g[b].eb(a, c);
	// pq : {first, second}->{edge cost, vertex id}
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.ep(0, 0);
	ll sum = 0; int cnt = 0;
	while (!pq.empty()) {
		auto a = pq.top(); pq.pop();
		if (v[a.s]) continue;
		v[a.s] = 1, cnt++, sum += a.f;
		for (const auto& i : g[a.s])
			if (!v[i.f] && i.s != a.s)
				pq.ep(i.s, i.f);
	}
	return (cnt == n ? sum : -1);
}

#### 範例程式碼 (Konchin)

inline void solve() {
//caculate MST weight sum
	int n,m;
	while(cin>>n>>m){
		vector<vector<edge>> e(n);
		for(int i=0;i!=m;i++){
			int a,b,w;
			cin>>a>>b>>w;
			e[a].emplace_back(b,w);
			e[b].emplace_back(a,w);
		}
		priority_queue<edge> pq;
		vector<bool> visited(n,false);
		pq.emplace(0, 0);
		long long sum=0;
		for(int i=0;i!=n;i++){ //at most n times (totally n vertices)
			int a=~0u; //-1
			while(pq.size()&&visited[a=pq.top().b])
				pq.pop();
			if(!~a) break;
			else sum+=pq.top().w,visited[a]=true;
			for(const auto& i:e[a])
				if(!visited[i.b])
					pq.emplace(i);
		}
		cout<<(*min_element(visited.begin(),visited.end())?sum:-1)<<endl;
	}
}

---