[Algorithm]Minimum Spanning Tree

对于给定的连通加权无向图G=(V, E), (u, v)代表连接顶点u和v的边，w(u, v)代表(u, v)的权重，若存在E的子集T，且(V, T )为树(无环)，使得：

• w(T) = sum(w(u, v)), where u,v in V

w(T)最小，则(V, T)是G的最小生成树。

从中我们可以看出最小生成树MST的几个性质，假设顶点数为n：

1. MST是连通的并且有n个顶点，n - 1条边
2. 如果我们插入一条边e(u, v)，e不属于T但是属于E，那么一定会形成一个环，因为u和v在最小生成树当中是连通的。并且e是环上的最长一条边，也就是说，G中存在的环，其环上最长一条边e一定不在MST当中。证明很简单，如果我们插入环上的另一条边并且去掉e，依然是连通的，并且总权值会下降。

计算MST一般有两种算法，Prim和Kruskal，我们对这两种算法分别讲解。

Prim

Prim算法的具体步骤为：

1. 维护一个集合VS，代表已经在MST当中的顶点; ES代表我们加入MST中的边
2. 从任意顶点u开始，把u加入VS，VS = {u}, ES = {}
3. 每一次从E中取出权值最小的边e(u, v)加入ES，并且把v加入VS，e满足条件其一个端点u在VS中，另一个端点v在V - VS中
4. 重复步骤3直到所有顶点放入VS，那么MST = (VS, ES)

如图所示(来自wiki)：

图例	说明	不可选	可选	已选
	此为原始的加权连通图。每条边一侧的数字代表其权值。	-	-	-
	顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。	C, G	A, B, E, F	D
	下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。	C, G	B, E, F	A, D
	算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。	C	B, E, G	A, D, F
	在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。	无	C, E, G	A, D, F, B
	这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。	无	C, G	A, D, F, B, E
	顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。	无	G	A, D, F, B, E, C
	现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。	无	无	A, D, F, B, E, C, G

Prim的思路其实就是动态地维护一个点和边的集合，VS和ES。我们每一次选的就是连接VS和V-VS两个集合的所有边当中最小的那一个。一直重复直到VS = V即可。证明我们稍后给出。

Kruskal

Kruskal算法的具体步骤为：

• 把所有边 按照权值从小到大sort，MST = (VS, ES)，起始VS = V，ES = {}
• 每次取剩余权值最小的边e，加入ES；如果e和VS, ES形成环，我们抛弃e
• 直到我们扫完所有的边，算法结束

过程如图所示(来自wiki):

图例	说明
	AD和CE是最短的两条边，长度为5，其中AD被任意选出，以高亮表示。
	现在CE是不属于环的最短边，长度为5，因此第二个以高亮表示。
	下一条边是长度为6的DF，同样地以高亮表示。
	接下来的最短边是AB和BE，长度均为7。AB被任意选中，并以高亮显示。边BD用红色高亮表示，因为B和D之间已经存在一条（标为绿色的）路径，如果选择它将会构成一个环（ABD）。
	以高亮表示下一条最短边BE，长度为7。这时更多的边用红色高亮标出：会构成环BCE的BC、会构成环DBEA的DE以及会构成环FEBAD的FE。
	最终，标记长度为9的边EG，得到最小生成树，结束算法过程。

我们可以用Union Find来查每次新加入的边会不会形成环。关于Union Find的讲解，可以参考这一篇文章。

算法证明

我们首先证明定理1

• 对于图G(V, E)，和顶点集合S，其中S既不为空集也不等于V。假设边的cost都不相同，其中存在e(u, v)，e属于E，e的一端在S另一端在V-S，并且e是满足条件cost最小的边，那么e一定在MST当中

假设存在最小生成树T，其不包含e。那么我们要证明加上e之后我们可以找到cost更小的MST，假设我们加上e。那么对于S和V-S，其在T当中肯定存在另一条边连通这两个集合，于是我们在T中加入e之后会形成一个环：

如图所示，假设在T中连接S和V-S的边为e'(v', w')，那么加入e之后e'和e肯定在相同的环上，因为v'和v在S当中是连通的，而w'和w肯定在V-S里也是连通的。如果我们把e'替换成e，T' = T - e' + e，那么T'肯定仍然是生成树，因为所有点仍然是连通的并且边的数目没有变。但是因为e的定义，显然T'的cost小于T。所以定理得证。

对于Prim算法来说，其每次在做的就是定理1的事情，每次取S和V-S的最小边。Prim最终的结果是一个生成树也是一个明显的结论。每一次都会把V-S中的一个节点和S相连，直到S = V。

Kruskal的证明是类似的，对于我们每次加入的边e(u, v)，我们把v和所有从v可达的节点看做S，那么u所在的节点肯定在V-S当中，因为加入e之后不会形成环。那么e一定是最小的，因为边是从小到大sort的，并且e是第一个我们遇到连接S和V-S的边。所以e一定在MST当中。

时间复杂度

Prim算法
我们用Priority Queue来维护每个节点到V的最小距离，每次从优先队列展开最小的即可。具体时间复杂取决于优先队列是怎么实现的，如果队列支持更新其元素优先级的话(比如java)，时间复杂度就为O(E * log V)，每一个节点只需要有一个对应的值在队列上就行了，对于每一个边我们都要check是否要更新一下优先队列，优先队列size最大为V。对于不支持更新队列的情况(比如c++)，我们就需要允许队列存在重复的节点，我们再在展开的时候去重。时间复杂度就为O(E * log E)。

Kruskal算法
sort边需要E * log E的时间，用Union Find check是否会形成环，每一次操作十分接近常数时间复杂度，每个边都要check，所以这一块的时间复杂度约等于E，所以总的实际复杂度为O(E * log E)。

实现

Prim

	#include <bits/stdc++.h>
	using namespace std;
	int prims(int n, vector < vector<int> > edges, int start) {
	//construct graph
	vector<vector<pair<int, int>>> g(n + 1);
	for(auto& edge : edges)
	{
	int weight = edge[2], from = edge[0], to = edge[1];
	g[from].push_back(make_pair(weight, to));
	g[to].push_back(make_pair(weight, from));
	}
	vector<bool> visited(n, false);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	//construct pq
	visited[start] = true;
	for(auto& e : g[start])
	if(!visited[e.second])
	pq.push(e);
	int totalW = 0;
	//total n-1 edges to select
	for(int i = 1; i < n; ++i)
	{
	while(visited[pq.top().second])pq.pop();
	auto e = pq.top();
	pq.pop();
	//we find an edge in MST
	totalW += e.first;
	visited[e.second] = true;
	//update edges on pq
	for(auto& e : g[e.second])
	if(!visited[e.second])
	pq.push(e);
	}
	return totalW;
	}
	int main() {
	int n;
	int m;
	cin >> n >> m;
	vector< vector<int> > edges(m,vector<int>(3));
	for(int edges_i = 0;edges_i < m;edges_i++){
	for(int edges_j = 0;edges_j < 3;edges_j++){
	cin >> edges[edges_i][edges_j];
	}
	}
	int start;
	cin >> start;
	int result = prims(n, edges, start);
	cout << result << endl;
	return 0;
	}

view raw hackerrank_Prim's (MST) : Special Subtree.cpp hosted with ❤ by GitHub

Kruskal

	#include <bits/stdc++.h>
	using namespace std;
	int root(int i, vector<int>& uf)
	{
	if (uf[i] == i)return i;
	int r = root(uf[i], uf);
	uf[i] = r;
	return r;
	}
	void connect(int i, int j, vector<int>& uf, vector<int> sz)
	{
	int rootI = root(i, uf), rootJ = root(j, uf);
	if(rootI == rootJ)return;
	if (sz[rootI] <= sz[rootJ])
	{
	uf[rootI] = rootJ;
	sz[rootJ] += sz[rootI];
	}
	else
	{
	uf[rootJ] = rootI;
	sz[rootI] += sz[rootJ];
	}
	}
	bool find(int i, int j, vector<int>& uf)
	{
	return root(i, uf) == root(j, uf);
	}
	int mst(int n, vector < vector<int> > edges) {
	int totalW = 0, count = 0;
	//initialize union find
	vector<int> uf(n + 1, 0), sz(n + 1, 1);
	for(int i = 1; i <= n; ++i)uf[i] = i;
	//sort edge based on cost
	auto comp = [](const vector<int>& lhs, const vector<int>& rhs){return lhs[2] < rhs[2];};
	sort(edges.begin(), edges.end(), comp);
	for(auto& edge : edges)
	{
	int from = edge[0], to = edge[1], weight = edge[2];
	if(find(from, to, uf))continue;
	//we find an edge
	totalW += weight;
	++count;
	connect(from, to, uf, sz);
	if(count >= n - 1)break;
	}
	return totalW;
	}
	int main() {
	int n;
	int m;
	cin >> n >> m;
	vector< vector<int> > edges(m,vector<int>(3));
	for(int edges_i = 0;edges_i < m;edges_i++){
	for(int edges_j = 0;edges_j < 3;edges_j++){
	cin >> edges[edges_i][edges_j];
	}
	}
	int result = mst(n, edges);
	cout << result << endl;
	return 0;
	}

view raw hackerrank_Kruskal (MST): Really Special Subtree.cpp hosted with ❤ by GitHub