maximal_matching#

maximal_matching(G)[source]#

在图中寻找极大匹配。

匹配是边的一个子集，其中没有节点出现多次。极大匹配是指无法添加更多边并仍然保持匹配状态的匹配。

参数:

GNetworkX graph

无向图

返回值:

matchingset

图的一个极大匹配。

备注

该算法贪婪地选择图 G 的一个极大匹配 M (即不存在 M 的超集)。它的时间复杂度为 $O(|E|)$。

示例

>>> G = nx.Graph([(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)])
>>> sorted(nx.maximal_matching(G))
[(1, 2), (3, 5)]