一、什么是最大生成树：
在一个图的所有生成树中边权值和最大的生成树即为最大生成树。
二、怎么生成：
1、将图中所有边的边权变为相反数，再跑一遍最小生成树算法。相反数最小，原数就最大。
2、修改一下最小生成树算法：对于kruskal，将“从小到大排序”改为“从大到小排序”；
对于prim，将“每次选到所有蓝点代价最小的白点”改为“每次选到所有蓝点代价最大的点”。
证明：对于修改后的kruskal，可以参照：kruskal算法证明及实现，下面是我个人应“最大生成树”的修改版：
证明如下：
假设最大生成树树为U。先做出如下假设：
1)按照算法得到的树为T。
2)U和T中不同的边的条数为k,其它n-1-k条边相同，这n-1-k条边构成边集E；
3)在T中而不在U中的边按代价从大到大依次为a1，a2，…，ak。
4)在U中而不在T中的边按代价从大到小依次为x1，x2，…，xk。
现在我们通过把U转换为T（把T的边依次移入U中），来证明U和T具有相同代价。
首先，我们将a1移入U中，由于U本身是一棵树，此时任意加一条边都构成回路，所以a1的加入必然产生一条回路，且这条回路必然包括x1，x2，…，xk中的边。（否则a1与E中的边构成回路，而E也在T中，这与T中无回路矛盾。）
在这个回路中删除属于x1，x2，…，xk且代价最小边xi构成一个新的生成树V。
假设a1代价大于xi，则V的代价大于U，这与U是最大代价树矛盾，所以a1不可能大于xi。
假设a1代价小于xi，按照修改版的Kruskal算法，首先考虑代价大的边，则执行算法时，xi应该是在a1之前考虑，而a1又在a2，…，ak之前考虑，所以考虑xi之前，T中的边只能是E中的边，而xi既然没加入树T，就说明xi必然与E中的某些边构成回路，但xi和E又同时在U中，这与U是生成树矛盾，所以a1也不可能小于xi。
因此，新得到的树V与U具有相同代价。即V也为最小生成树，不过V比U更“靠近”T（不同的边更少），这时让U代表现在的V，再走一遍上面的流程，把a1，a2，…，ak的边逐渐加到U中，最终得到的树即为T，且与U代价相同。
证明结束。
对于修改后的prim，可以参照：Prim算法和Kruskal算法的正确性证明（参照一下就好），下面是我个人的简单证明：
prim算法之所以可行，是基于这样一个判断：对于任意一个顶点vi，连接到该顶点的所有边中的一条最短边（最大生成树则为最长边）(vi, vj)必然属于最小生成树（最长边必然属于最大生成树）（该判断也可以扩展成：任意一个属于最小（或大）生成树的连通子图（子树），从外部连接到该连通子图的所有边中的一条最短边（或最长边）必然属于最小（或大）生成树）
证明如下（这里以最大生成树为例）：设当前点为u，连接到该点所有边中最长边的一条为a，用反证法证明，假设最长边不在最大生成树U中：
若把a再加到最大生成树中，必然会成环。此时在这个环上必然有两条边连接着u，一条边为a（刚加进去），设另一条边为b，显然b的权值小于a（因为b不是最长边，所以b的权值不会等于a），那么把b从环中删去，得到的生成树的权值和会比U更大，与U是最大生成树矛盾。
对于一个已知点的连通子图（子图点之间的边不重要，因为不会影响子图与外部链接的最长边），仍用反证法证明，假设与外部连接的最长边不在最大生成树U中：
设该子图与外部连接的最长边的一条为a，把a加到最大生成树中，必然会形成环，环上必然有两条边连接着这个子图，一条边为a，设另一条为b，则b的权值小于a，那么把b从环里删去，新得到一个生成树的权值比U更大，与U是最大生成树矛盾。
今天的文章浅谈最大生成树分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/46305.html
