hopcroft_karp_matching

hopcroft_karp_matching(G, top_nodes=None)

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

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

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

Parameters:

GNetworkX 图

无向二分图

top_nodes节点容器

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

Returns:

matches字典

匹配结果以字典 matches 形式返回，使得 matches[v] == w 如果节点 v 与节点 w 匹配。未匹配的节点不会作为 matches 的键出现。

Raises:

AmbiguousSolution

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

See also

maximum_matching

hopcroft_karp_matching

eppstein_matching

Notes

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

有关二分图在 NetworkX 中处理的更多细节，请参阅 二分图文档 。

References

[1]

John E. Hopcroft 和 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>.