在Coursera的Standford算法上有一题是让实现Karger’s Random Contraction Algorithm for Min Graph Cuts.
粗略的给出了一个实现，优化空间非常大。现在记录一下遇到的问题。 Karger’s Random Contraction Algorithm主要思想就是随机选择一条边，把这条边的两个node合并，一直到只剩下两个节点，节点之间的边数就是这个cut经过的边数。这样就随机得到图的一个cut，那么最小cut怎么得到呢？重复这个步骤多次，得到的最小的cut就认为是这个图的最小割，理论上可以证明这个概率还是很大的。
在实现Karger’s Random Contraction的时候首先是数据结构的选择，因为使用邻接表的存储方式，所以我考虑使用一个二维数组vector<vector <int>> 按给的邻接表数据来存储。
每次随机的时候，先随机选择一个node，然后在这个node的临近边中随机选择一条边<node,_node>，最后把_node合并到node上。
合并的时候：
_node的替换成node_node的连接表添加到节点_node上_nodenode节点的环(即自己指向自己)因为使用的是vector<vector <int>>数据结构，所以在上面步骤1的时候需要注意的问题是：
_node节点后面会被删除，索引会改变_node的节点索引都要减去一个1_node，进行减1操作 替换成node的时候也要考虑是替换成node or node-1合并步骤基本就完了，然后就是不断进行合并直到节点数为2.
代码在Gist上https://gist.github.com/HaiyangXu/93df14ae616adc764ee6
想过的优化：
_node的时候时间复杂度就只有logn，但是因为索引要改变，不管你排不排序都要全部遍历一遍，干脆不用排序了，也不用链表随机性： 使用rand得到的随机一点也不随机，后面研究一下随机数生成问题。