eppstein_matching

eppstein_matching(G, top_nodes=None)

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

Parameters:

GNetworkX 图

无向二分图

top_nodes容器

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

Returns:

matches字典

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

Raises:

AmbiguousSolution

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

See also

hopcroft_karp_matching

Notes

此函数采用 David Eppstein 版本的 Hopcroft–Karp 算法（参见 hopcroft_karp_matching() ）实现，该算法最初出现在 Python 算法和数据结构库 (PADS) 中。

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