带花树算法一般图最大匹配
带花树算法的最大图匹配方式，效率还挺高的，适合一般图中找最大匹配的问题。它其实就是一种通过找“增广路径”来不断优化匹配的方法，而且对奇环结构的也比较巧妙，用了“收缩”再“释放”的思路，边改边算，逻辑虽然有点绕，但实现下来还蛮清晰的。
Jack Edmonds 早在 1955 年就整了这套逻辑，叫Blossom 算法。说白了就是先贪心抓一把能配上的边，开个BFS去找有没有可以再多配一对的路径。碰上奇环的时候，就把它们当成一个“花”，用contract函数收起来，路径走通了再用expand放出来，整得还挺灵活。
配套的结构设计也比较合理，比如head搞邻接表，base标顶点归属，match记录谁配对了谁，还有一堆inblossom、inpath用来标状态。这些细节要是不好，代码跑起来就容易乱套。
性能方面，原版的复杂度是O(V^4)，确实不低，不过在图规模不是爆炸的情况下，实际用着也还行。网上也有些提到可以优化到O(V^3)，但那是建立在一些图结构或者做了额外假设的前提下，别太当真。
如果你正好在搞任务分配、网络配对、社交推荐这类场景，带花树这个方法确实值得一试，代码写起来稍微绕点，但跑出来的效果还是挺靠谱的。实在搞不清楚结构关系，可以多看看源码例子和可视化工具。
文件大小：15.16KB
评论区