本文主要是介绍Kernighan-Lin算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
注意：之前对于公式用LATEX编写，复制的图片，不知怎么就显示不出，凡是框框的地方，用文字表示了公式。 输入：一个待划分的图G=(V,E，C)
输出：划分A和B
1. 给定一个初始划分A和B
2. do
3. A(1)=A; B(1)=B;
4. 对A(1)和B(1)中的每一个节点计算其D值；
5. for （p=1 to |V|/2）
6. A(p)中选出ai，Bp中选出和bj，使得![Kernighan-Lin算法]( "Kernighan-Lin算法")
gain(p)=Dai+Dbj-2Caibj为最大值；
7. ap'=ai；bp'=bj；A(p+1)=A(p)-ap'；B(p+1)=B(p)-bp'；
8. p=p+1;
9. 更新A(p)和B(p)中每个节点的D值；
10. end for
11. 选择k使得![Kernighan-Lin算法]( "Kernighan-Lin算法")
G=求和gain(i) 为最大值（k为gain(i)为正值的个数）；
12. if (G>0)
13. 把A中的a1',a2',...,ak'与B中的b1',b2',...,bk'进行交换；
14.until (G<=0)
15.return A，B
1-(1-p)^(kt/t')![Kernighan-Lin算法]( "Kernighan-Lin算法")
。那么只要是的后者大于前者即可。
（2）将kn个节点划分为n个节点和(k-1)n个节点的两个社区，之后对(k-1)n个节点的社区再划分为n个节点和(k-2)n个节点的社区，如此往复下去。
参考文献：
1.维基百科对Kernighan-Lin算法的解释：http://en.wikipedia.org/wiki/Kernighan–Lin_algorithm
2.Karypis G, Kumar V. Multilevel< i> k</i>-way Partitioning Scheme for Irregular Graphs[J]. Journal of Parallel and Distributed computing, 1998, 48(1): 96-129.
声明：后半部分，由于文章阅读较浅显，所以可能含有一些错误，希望 大家指出。
这篇关于Kernighan-Lin算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
