点击打开链接
最大权匹配
KM算法
算法步骤:
设顶点Xi的顶标为a[i],顶点Yi的顶标为b[i]
ⅰ.初始时,a[i]为与Xi相关联的边的最大权值,b[j]=0,保证a[i]+b[j]>=w(i,j)成立
ⅱ.当相等子图中不包含完备匹配时,就适当修改顶标以扩大相等子图,直到找到完备匹配为止
ⅲ.修改顶标的方法
当从Xi寻找交错路失败后,得到一棵交错树,它的所有叶子节点都是X节点,对交错树中X顶点的顶标减少d值,Y顶点的顶标增加d值,对于图中所有的边(i,j),
可以看到:
i和j都不在交错树中,边(i,j)仍然不属于相等子图
i和j都在交错树......
阅读全文