python - 图中最小割的随机收缩算法

Question

我试图编写一个 Karger 算法的实现来解决最小切割问题。这是我的代码

def randomVertices(g): 
    v1 = g.keys() [random.randint(0,len(g)-1)]
    v2 = g[v1] [random.randint(0,len(g[v1])-1)]
    return v1, v2


def mergeVertices(g):
    v1,v2 = randomVertices(g)

    g[v1].extend(g[v2])

    for x in g[v2]:
        l = g[x]
        for i in range(0,len(l)):
            if l[i] == v2: 
                l[i] = v1        

    while v1 in g[v1]:
        g[v1].remove(v1)

    del g[v2]

def minCut(g): 
    while len(g) > 2: 
        mergeVertices(g)
    return len(g[g.keys()[0]])

它没有评论，但它应该是不言自明的。'g' 是一个字典，其键是图的顶点，每个顶点的值都是它所连接的顶点。randomVertices 为我提供了我想要收缩的边缘，而 mergeVertices 通过删除第二个顶点、更新链接到该顶点的键的值以及摆脱自循环来更新字典（以及因此的图形）。对我来说它看起来不错，但如果我在任何测试图上运行它，我会在l = g[x]舞台上得到一个 KeyError，我不明白为什么会发生这种情况。希望你们中的一些人可以帮助我。谢谢。

编辑：我的代码实际上很好，错误在于我使用相邻列表加载文件的方式。Cobarzan，谢谢你指出我实际上并没有统一挑选边缘。