在 C 或 Python 中是否有现成的最大基数二分匹配的快速实现？
我试过 networkx，但速度很慢。我有一个两层图，每层大约有 1000 个节点。密度不同。此设置的预期时间是多少？
我看到这篇文章 Fast max-flow min-cut library for Python , 但有什么更快的吗？
最佳答案
SciPy ，从版本 1.4.0 开始，在 scipy.sparse.csgraph.maximum_bipartite_matching 中包含 Hopcroft--Karp 的实现，在性能方面与 NetworkX 相比毫不逊色。该功能也存在于以前的版本中，但随后假设完美匹配；这个假设在 1.4.0 中取消了。
它到底有多好将取决于二分图的结构，但仅通过随机图(并忽略 NetworkX 初始化底层数据结构所需的时间)，我获得了大约 200 倍的性能改进:
import networkx as nx
from scipy.sparse import rand
from scipy.sparse.csgraph import maximum_bipartite_matching
n = 5000
graph = rand(n, n, density=.1, format='csr', random_state=42)
G = nx.algorithms.bipartite.from_biadjacency_matrix(graph)
>>> %timeit maximum_bipartite_matching(graph, perm_type='column')
8.95 ms ± 183 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
>>> %timeit nx.algorithms.bipartite.maximum_matching(G, top_nodes=range(n))
2.01 s ± 118 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
关于python - C 或 Python 中的快速最大二分匹配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49524937/