我自己大概看懂了最大流最小割问题,但是看完之后我发现不是我想找的算法,我想找将加权图二分的算法(又叫最小截断),划分后两个子图大小差不多等且割断的边权重和最小。我查了资料这个算法好像叫hMETIS,但是具体代码还是不知道,不知道你知道不啊。。。谢谢。
追答囧...不会hmetis算法,sorry
但是"割断的边权重和最小"说的确实是最小割
最小割的确是图割断的边权重最小,但好像没有将图分成两个子图,他只是使源点和汇点之间没有通路,我不知道最小割应用到无向加权图会是怎样,我也是刚接触图论方面的知识~
追答他分成2个部分了,所谓的割, 是一个边的集合, 对于集合里面的任意边 a->b a跟b都不在一个集合里, 还有最大流不存在无向图的问题, 流是不可能没有方向的 , 你指的无向图其实是2个有向边