要么改变世界,要么适应世界
该标签下的文章

利用KM算法求解最大权匹配

2020-11-27 13:28:00
89
算法

`KM`算法是一种计算机算法,功能是求完备匹配下的最大权[匹配](https://baike.baidu.com/item/匹配/6397551)。在一个二分图内,左顶点为`X`,右顶点为`Y`,现对于每组左右连接`Xi->Yj`有权`wij`,求一种匹配使得所有`wij`的和最大 ...

匈牙利算法求解二分图的最大匹配

2020-11-27 13:24:12
115
算法

设`G=(V,E)`是一个无向图,如果顶点`V`可分割为两个互不相交的子集`(A,B)`,并且图中的每条边`(i,j)`所关联的两个顶点`i`和`j`分别属于这两个不同的顶点集`(i in A,j in B)`,则称图`G`为一个二分图。 ...