假设我对计算生成树有三种限制：
约束度（例如：
生成树只能是
最多连接3个其他节点）
有界直径（例如：所有边
权数相加后不能超过
100页）。
2.1。如果可能，显示符合此条件的所有子树。
两者
有没有什么好的算法可以解决这个问题，不会让我发疯我必须用相当大的输入（1000 +节点）来运行，所以它的复杂度也不能太高。
最佳答案
度约束生成树问题是np完全问题。见http://en.wikipedia.org/wiki/Degree-constrained_spanning_tree。
所以，没有好的（即多项式）算法。不过，也有近似算法。
google搜索似乎表明，有界直径生成树问题同样困难。
关于algorithm - 约束度+有界直径最小生成树的算法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3340406/