Kernighan-Lin
Kernighan-Lin算法
算法伪代码
输入 待划分的大图G=(V,E)
输出 划分后子图A、B
1、将图G平均划分为A、B两个初始子图
do
计算A、B子图中各个节点的D_values值
for i in range(|V|/2)
从A和B两个子图中，分别找出a、b，使得gain=D_values[a] + D_values[b] - (2 * c_ab)最大
将a、b移除，不参与后面过程；将a、b、gain存入gains[]
更新A、B子图各个节点的D值
end for
计算g_max以及使得g_max最大的k值
if g_max > 0 then
交换A、B子图顶点
until 没有可以交换的顶点对之后算法结束，此时g_max小于0
数据使用空手道俱乐部社交关系图，共有34个节点和78条边