二分图最小边覆盖

Question

我正在寻找一种简单的算法，用于在二分图中获取最小加权边。我已经搜索了很多资料，所知道的全部意味着二分图的覆盖边，换句话说，如果我们有一个二分图，并且每个边都有一个数字权重，如何获取它们之间的最小值。

- esraaelsayed

---

我假设您正在询问二分图的最小加权顶点覆盖？ - mindvirus

不，它不是顶点，而是边。我找到了许多关于加权顶点的算法，但这不是我需要的。 - esraaelsayed

如果你的问题只是“二分图边缘中的最小权重边”，那么只需迭代图的边缘并取最小值即可。但这似乎不是我理解你的问题 - 你能给一个例子吗？ - mindvirus

Answer 1

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

- mmgp

Answer 2

你需要使用匈牙利算法。 点击这里 获取讲义笔记。

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

---

1. 从每行中减去最小条目
2. 从每列中减去最小条目
3. 通过适当的行和列绘制线，以便覆盖成本矩阵的所有零条目并且使用最少数量的线
4. 测试最佳情况： (1)如果覆盖线的最小数量为n，则可能存在最佳分配，我们已完成。(2) 如果覆盖线的最小数量小于n，则尚未达到零的最佳分配。转到步骤5。
5. 确定未被任何线覆盖的最小条目。从每个未被覆盖的行中减去该条目，然后将其添加到每个已覆盖的列中。返回步骤3。

---

上述算法基于一个数学定理：

• 如果在成本矩阵的任意一行或一列的所有条目中加上或减去一个数字，则结果成本矩阵的最优分配也是原始成本矩阵的最优分配。

- renqHIT

Answer 3

除了其他答案中提到的匈牙利算法，更好的选择是Jonker-Volgenant（LAPJV）算法。

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

它非常快速，能够在不到一秒钟的时间内完成1000到1000的计算。

该库还包括贪心搜索，速度更快，但不能保证最优解。

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

- dberm22