graph-theory - 二分最小边

Question

我正在寻找一种简单的算法来获得二分图的边中的最小加权边。我搜索了一下，我都知道这意味着二分图的覆盖边，换句话说，如果我们有二分图并且每条边都有一个数字权重，如何获得其中最小的数字

Answer 1

提出这个问题的方式使其非常不清楚。我从中得到的一种解释是：“给定一个加权二部图 G，我如何获得 G 的最小边覆盖？”。如果是这种情况，那么匈牙利算法（参见http://reference.wolfram.com/mathematica/ref/FindEdgeCover.html也可以解决您的问题。

Answer 2

你需要匈牙利算法。单击此处 获取讲义。

在处理之前，你应该有一个成本矩阵，其中每个条目是从节点A到节点B的边成本。匹配步骤如下：

---

1. 减去每行中最小的条目
2. 减去每列中最小的条目
3. 通过适当的行和列画线，以便覆盖成本矩阵的所有零条目并使用此类线的最小数量
4. 最优测试：（1）如果覆盖线的最小数量为n，则最优分配是可能的，我们就完成了。(2) 如果覆盖线的最小数量小于 n，则零的最佳分配是不可能的。转到第 5 步。
5. 确定未被任何行覆盖的最小条目。从每个未覆盖的行中减去该条目，然后将其添加到每个已覆盖的列。返回步骤 3。

---

上面的算法是基于一个数学定理

• 如果一个数字被添加到成本矩阵的任何一行或一列的所有条目中或从其中减去一个数字，则结果成本矩阵的最佳分配也是原始成本矩阵的最佳分配。

Answer 3

Jonker-Volgenant ( LAPJV ) 算法甚至比其他答案中建议的匈牙利算法更好。

看看这个名为Bipartite Solver的 GitHub 存储库，它基本上是一个关于如何在代码中实现 LAPJV 的教程，并带有一个可运行的图形示例。

它的速度非常快，能够在一秒钟内完成 1000 到 1000 次。

库中还包括贪心搜索，它甚至更快，但不能保证最优性。

如果您想尝试算法而不必从源代码构建它，该库还有一些可执行文件。