图——最小生成树——kruskal算法

1. 最小生成树

1.1. kruskal算法

kruskal算法&＃xff0c;就是一个贪心的思想。从小到大&＃xff0c; 加入符合条件的边。

1.1.1. 步骤

1. 新建图G&＃xff0c; G中拥有原图中相同的节点&＃xff0c; 但没有边
2. 将原图中所有的边按权值从小到大排序
3. 从权值最小的边开始&＃xff0c;如果这条边连接的两个节点于图G中不同一个连通分量中&＃xff0c; 则添加这条边到图G中。
4. 重复3&＃xff0c;直至图G中所有的节点都在同一个连通分量中

1.1.2. 证明

1. 这样的步骤保证了选取的每条边都是桥&＃xff0c;因此图G构成一个树。
2. 为什么这一定是最小生成树呢&＃xff1f;关键还是步骤3中对边的选取。算法中总共选取了n-1条边&＃xff0c;每条边在选取的当时&＃xff0c;都是连接两个不同的连通分量的权值最小的边
3. 要证明这条边一定属于最小生成树&＃xff0c;可以用反证法&＃xff1a;如果这条边不在最小生成树中&＃xff0c;它连接的两个连通分量最终还是要连起来的&＃xff0c;通过其他的连法&＃xff0c;那么另一种连法与这条边一定构成了环&＃xff0c;而环中一定有一条权值大于这条边的边&＃xff0c;用这条边将其替换掉&＃xff0c;图仍旧保持连通&＃xff0c;但总权值减小了。也就是说&＃xff0c;如果不选取这条边&＃xff0c;最后构成的生成树的总权值一定不会是最小的。

1.1.3. 时间复杂度

平均时间复杂度为O(|E|log|V|)&＃xff0c;其中E和V分别是图的边集和点集。

1.1.4. 伪代码

KRUSKAL-FUNCTION(G, w)
1 F :&＃61; 空集合//起初每个顶点为一棵只有一个节点的树。
2 for each 图 G 中的顶点 v
3 do 将 v 加入森林 F
4 所有的边(u, v) ∈ E依权重 w 递增排序
5 for each 边(u, v) ∈ E
6 do if u 和 v 不在同一棵子树
7 then F :&＃61; F ∪ {(u, v)}
8 将 u 和 v 所在的子树合并


1.1.5. CPP模板

对于1.1.2中的第三步&＃xff0c;我们可以通过并查集来确定一条边的两个端点是否在同一个连通分量。

const int MAXN &＃61; 110;//最大点数
const int MAXNM &＃61; 1e4; //最大边数struct Edge{int u;//端点1int v;//端点2int w;//权值
};
//边集数组
vector<Edge>edge;//并查集&＃xff1a;并查集使用
int par[MAXN];//并查集&＃xff1a;初始化操作
void makeSet(){for(int i &＃61; 0;i < MAXN;i&＃43;&＃43;)par[i] &＃61; i;
}//并查集: 查找节点的根.
int Find(int x){if(par[x] &＃61;&＃61; x)return par[x];else return par[x] &＃61; Find(par[x]);
}//并查集&＃xff1a;合并两个节点
void Union(int x, int y){int rootx &＃61; Find(x);int rooty &＃61; Find(y);if(rootx !&＃61; rooty)par[rootx] &＃61; rooty;
}//排序函数
bool cmp(Edge a, Edge b){return a.w < b.w;
}int Kruskal(int n){makeSet();int cnt&＃61;0; //计算加入的边数int ans &＃61; 0;//1.排序sort(edge.begin(),edge.end(), cmp); /**2.从权值最小的边开始&＃xff0c;如果这条边连接的两个节点于图G中不同一个连通分量中&＃xff0c; 则添加这条边到图G中。**/for(int i &＃61; 0;i < edge.size();i&＃43;&＃43;){int u &＃61; edge[i].u;int v &＃61; edge[i].v;int w &＃61; edge[i].w;if(Find(u)!&＃61; Find(v)){Union(u, v);ans&＃43;&＃61;w;cnt&＃43;&＃43;;}if(cnt &＃61;&＃61; n - 1)break;}if(cnt < n-1) return -1; //不连通&＃xff0c;不能产生最小生成树else return ans;
}

参考

1. kuangbin板子
2. 维基百科克鲁斯克尔算法
3. OI-WiKi