我希望设计一个算法。在一个有向图G=（V,E）中，每条弧都有一个数值权重。该算法需要返回一组最大权重的弧集S，使得其中任意两个弧的起点不相同。假设这个图至少有7个节点和10条弧。是否有人可以给出有关此算法的一些提示？
1个回答
2
您说弧不允许有相同的尾部。因此，我会将弧集分成几个“箱子”，这些箱子由弧的尾部确定。也就是说，您取每个弧，查看其尾部，并将其放入相应的箱子中。
考虑以下弧组成的图：
(1->2)
(1->3)
(2->1)
(2->4)
(3->2)
然后，我们有以下内容：
bin 1 | 2 | 3 | 4
arc 2 3 | 1 4 | 2 | (empty)
weight .. .. | .. .. | .. |
现在很明显，我们最多只能从每个箱子中选取一条弧。为了使总和最大化，我们可以始终选择每个箱子中权重最大的一个弧。
编辑：请注意，您的算法不需要做整个箱子的操作。它可以直接遍历所有弧，并动态更新解决方案。
- phimuemue
3
1请注意，在这种情况下，每个“bin”实际上只是图中的一个节点，因此您要做的就是遍历节点列表并选择具有最大权重的出边。此外，我不建议遍历整个图，因为似乎不能保证图是连通的。 - B_.
@B_ 我不建议沿着图的连接遍历，而是建议遍历弧列表。 - phimuemue
我的错误，误解了你的建议。 - B_.
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接