maximal_matching

maximal_matching(G)

在图中找到最大匹配。

匹配是边缘的子集，其中没有节点出现多次。最大匹配不能添加更多的边，并且仍然是匹配的。

参数

G网络X图表

无向图

返回

matching设置

图的最大匹配。

笔记

该算法贪婪地选择图G的一个最大匹配M(即不存在M的超集)。它跑进了 \(O(|E|)\) 时间到了。