karger算法求最小cut

cut就是指把一个图的结点分为两个集合，那么其中一些边的端点是分属两个集合的，使这种边数量最小的划分就叫minimum cut。

karger的算法是个randomnized algorithm，思路是随机找一个边，把这个边的两个端点融合为一个结点，把多余的点和边删除。

注意如果融合后的新结点出现self loop，那么是要删除这个self loop的，但是只是和其他结点形成平行边，那么这些平行边当然是不可以删除的。

最后合并到只剩两个点的时候，就相当于把原来的图的结点分为了两个集合，剩下的边就是这时的cut了。

当然这个算法正确的概率只有1/n^2，所以是需要多次重复来得到最好结果的，假设图有n个结点，那么运行n^2ln（n）次，错误概率会降为仅有1/n。

还是老问题：看着思路很简单，写起来就很烦，主要是对结点和边的操作简直要命，而且最后得到的实现也只是个o（n^2）的，见了鬼了。而且也没有很省空间，为了遍历+删除的list操作，开了很多新list，感觉蠢的要死，还是得赶紧学会fuctional programming啊。

import random

def readfile():
    '''
    读文件
    '''
    pass

def randomcut(adict):
    '''
    生成两个随机数，返回随机数决定的两个字符串
    '''
    a = random.randrange(0, len(adict))
    b = random.randrange(0, len(adict[list(adict.keys())[a]]))
    return (list(adict.keys())[a], adict[list(adict.keys())[a]][b])


def newadict(adict, vertex1, vertex2):
    '''
    把随机决定的那两个字符串代表的结点融合（这个模块写的简直要了老命了）
    '''
    list1 = adict[vertex1][:]
    list2 = adict[vertex2][:]
    for i in list1:
        if i == vertex2:
            adict[vertex1].remove(i)
    for j in list2:
        if j == vertex1:
            adict[vertex2].remove(j)

    for a in adict[vertex2]:
        if a != vertex1 :
            for m in adict[a]:
                if m == vertex2:
                    adict[a].remove(vertex2)
                    adict[a].append(vertex1)
                    adict[vertex1].append(a)

    adict.pop(vertex2)
    return adict


def mincut(adict):
    '''
    主程序，融合到只剩两个结点的时候停止
    '''
    if len(adict) == 2:
        return (len(adict[list(adict.keys())[0]]), len(adict[list(adict.keys())[1]]), adict)
    else:
        (vertex1, vertex2) = randomcut(adict)
        adict2 = newadict(adict, vertex1, vertex2)
        return mincut(adict2)


def main():
    '''
    运行100次主程序，返回最小的mincut
    '''
    templist = []
    for a in range(100):
        adict = readfile()
        b = mincut(adict)
        temp = b[0]
        templist.append(temp)
    print(templist)
    print(min(templist))

main()