hopcroft_karp_matching

hopcroft_karp_matching(G, top_nodes=None)

返回二分图 G 的最大基数匹配。

匹配是一组不共享任何节点的边。最大基数匹配是边数最多的匹配。它不总是唯一的。在二分图中寻找匹配可以被视为一个 networkx 流问题。

函数 hopcroft_karp_matching 和 maximum_matching 是同一函数的别名。

参数:

GNetworkX 图

无向二分图

top_nodes节点容器

包含一个二分节点集中的所有节点的容器。如果不提供，将计算得出。但如果存在多个解决方案，则会引发异常。

返回:

matches字典

匹配以字典形式返回，即 matches，其中如果节点 v 与节点 w 匹配，则 matches[v] == w。未匹配的节点不会出现在 matches 的键中。

引发:

AmbiguousSolution

如果输入的二分图不连通且未提供包含一个二分集中所有节点的容器，则引发此异常。当输入的图不连通时，确定每个二分集中的节点可能有多个有效解决方案。

另请参阅

maximum_matching

hopcroft_karp_matching

eppstein_matching

注意

此函数使用适用于二分图的Hopcroft-Karp 匹配算法实现。

有关 NetworkX 中如何处理二分图的更多详细信息，请参阅二分图 文档。

参考文献

[1]

John E. Hopcroft and Richard M. Karp. “An n^{5 / 2} Algorithm for Maximum Matchings in Bipartite Graphs” In: SIAM Journal of Computing 2.4 (1973), pp. 225–231. <https://doi.org/10.1137/0202019>.