问候溢出者，
我有一个加权有向图，我想要覆盖所有节点的最低成本树，其中根是图的特定给定节点。我不知道我是否也可以在每个节点上设置不同的最大分支，其中从该节点到其他节点（向外边缘）的分支数等于或小于该最大值？
那么最适合我开始阅读需求的算法是什么？我希望它足够快:)
非常感谢 ！
问问题
225 次
1 回答
9
您正在寻找有向最小生成树（树状），这是一种最佳分支。
http://en.wikipedia.org/wiki/Chu%E2%80%93Liu/Edmonds_algorithm
于 2011-05-28T12:09:59.017 回答