最小生成树
给定一个无向图，如果它的某个子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树，如果边上有权值，那么使得边权和最小的生成树叫做最小生成树。 常见的求解最小生成树的算法有Kruskal算法和Prim算法，生成树是否存在和图是否连通是等价的，所以假定图是连通的。
Prim算法
假设有一棵只包含一个顶点v的数T，然后贪心地选取T和其他顶点之间相连的最小权值的边，并把它加到T中。不断进行这个操作，，就可以得到最小生成树了(可用反证法证明)
不使用Heap优化的代码
int eg[max_v][max_v];int mincost[max_v];bool used[max_v];int V;int prim(){for(int i = 0 ; i < V ; i ++) {used[i] = false;mincost = INF;}mincost[0] = 0;int res = 0;while(true) {int v = -1;for(int i = 0 ; i < v ; i ++) {//从不属于已选边中选一个权最小的if(!used[i]) {if(v == -1 || mincost[i] < mincost[v]) v = i;}}if(v == -1) break;used[v] = true;res += mincost[v];for(int i = 0 ; i < V ; i ++) {mincost[i] = min(mincost[i],eg[v][i]);}}return res;}
prim算法也可以使用优先队列(堆)来维护，复杂度可以达到O(|E|log|V|)
Kruskal算法
按照边的权值顺序从小到大查看一遍，如果不产生圈(重边也算在内)，就把当前这条边加入到生成树中。 判断是否在一个连通分量中可以使用并查集。 整个Kruskal算法复杂度O(|E|log|V|)
struct edge {int from,to,cost;};bool cmp(edge a,edge b){return a.cost < b.cost;}edge eg[max_e];int v,e;int kruskal(){sort(eg,eg+e,cmp);init_union_find(v);int res = 0;//最小生成树权值for(int i = 0 ; i < e ; i ++) {edge e = eg[i];if(!same(e.from,e.to)) {unite(e.from,e.to);res += e.cost;}}}
有希望在的地方，痛苦也成欢乐
