讨论/技术交流/关于最小生成树的问题/
关于最小生成树的问题

问题

请问常用的最小生成树算法在加入n叉的限制之后,是否还可以证明正常工作

例子

比如在堆+unions find的算法中,除了判断两个节点是否在相同连通集中,同时加入对当时两节点的边数数量小于n的条件。
这个算法还可以保证正确工作吗?

共 2 个回复

感谢大佬回答。 查了一下这个问题似乎叫 degree-constrained minimum spanning tree,估计是np-hard了。

显然这样改造的Kruscal不可行。比如点A只和点B相连,但是这条边边权是最大的,点B和其他任意点都相连,按照你说的办法来做那就是没有生成树,但显然不是这样。