[ Minimum Spanning Tree, kruskal, prim ] 最小生成樹經典演算法

以前覺得這應該是很簡單的東西，但我發現網路上使用priority_queue的prim演算法相關程式碼我覺得寫不好，我就把我自己的放上來。這裡順便也放上kruskal的程式碼。

prim $\ord{\left(\abs{V}+\abs{E}\right)\log{\abs{V}}}$:

	template<typename T>
	class prim{
	static const int MAXN=100005;
	struct edge{
	int u, v;
	T cost;
	edge(){}
	edge(int u,int v,const T &cost):u(u),v(v),cost(cost){}
	bool operator< (const edge&b)const{
	return cost > b.cost;
	}
	};
	int n;// 1-base
	vector<edge> E;
	vector<int> G[MAXN];
	bool vis[MAXN];
	T build(int x){
	T ans = 0;
	priority_queue<edge> q;
	for(auto i: G[x]) q.push(E[i]);
	vis[x] = true;
	while(q.size()){
	edge e = q.top(); q.pop();
	if(vis[e.v]) continue;
	ans += e.cost;
	vis[e.v] = true;
	for(auto i:G[e.v]) if(!vis[E[i].v]){
	q.push(E[i]);
	}
	}
	return ans;
	}
	public:
	void init(int _n){
	n = _n;
	for(int i=1; i<=n; ++i) G[i].clear();
	}
	void addEdge(int u, int v, const T &cost){
	G[u].emplace_back(E.size());
	E.emplace_back(u, v, cost);
	G[v].emplace_back(E.size());
	E.emplace_back(v, u, cost);
	}
	pair<T,int> solve(){
	T ans = 0;
	int component = 0;
	for(int i=1; i<=n; ++i) vis[i] = false;
	for(int i=1; i<=n; ++i) if(!vis[i]){
	ans += build(i);
	++component;
	}
	return {ans, component};
	}
	};

view raw prim.cpp hosted with ❤ by GitHub

kruskal $\ord{\abs{V}+\abs{E}\log{\abs{E}}}$:

	template<typename T>
	class kruskal{
	static const int MAXN=100005;
	int n; // 1-base
	tuple<T,int,int> edge;
	int pa[MAXN];
	int find(int x){
	if(x==pa[x]) return x;
	return pa[x] = find(pa[x]);
	}
	public:
	void init(int _n){
	n = _n;
	}
	void addEdge(int u,int v,const T &cost){
	edge.emplace_back(cost, u, v);
	}
	pair<T,int> solve(){
	T ans = 0;
	int component = n;
	for(int i=1; i<=n; ++i) pa[i] = i;
	sort(edge.begin(), edge.end());
	for(const auto &e: edge){
	int u = find(get<1>(e)), v = find(get<2>(e));
	if(u==v) continue;
	pa[u] = v;
	ans += get<0>(e);
	}
	return {ans, component};
	}
	};

view raw kruskal.cpp hosted with ❤ by GitHub