生成树小总结

无向图最小生成树

Prim算法

这个实现做的非常不好,需要改进。对付稠密图,Prim更胜Kruskal一筹。

Kruskal算法

[这个实现等待填坑]

Borůvka算法

[这个实现等待填坑]

有向图最小生成树(最小树形图)

复杂度O(V * E),以下代码仅存储边,而且会对存储结构发生破坏,请注意。实现来源于国立台湾师范大学。我对这份代码进行了更加详细的注释。

适用于固定了生成树的根的情形

适用于生成树的根无法确定的情形

引用自GentieH,谢谢。

建立虚拟节点x,令x连所有的点,权值为所有边权的总和+1,求得最后结果减去该值即可,由于虚拟节点的存在,不会显式地出现孤立点,这时通过判断如果存在多与1个节点的pre为root,则说明无解。如果需要求出根节点,由于之前将x与图中的点连边时,我们按顺序连的话,考虑到可以用边去标识点,对于每一个终点v,如果它的pre为root,则标记这条边who,在求结果时,让who-E即可。

要求输出方案的情形

CF240E

 

次小生成树

[Pending Session]

增量最小生成树

[Pending Session]

最小瓶颈生成树

[Pending Session]

生成树问题混杂其他类型问题

Leave a Reply

Scroll to top