0

我已经为这个问题写了一些代码。(python27)

图形表示为具有 freezeset 键和 freezeset 集的字典：

sample_graph = {frozenset([7]): set([frozenset([4]), frozenset([5]), frozenset([3])]), frozenset([5]): set([frozenset([7]), frozenset([2]), frozenset([1])]), frozenset([3]): set([frozenset([7]), frozenset([4]), frozenset([2]), frozenset([1])]), frozenset([6]): set([frozenset([4]), frozenset([2]), frozenset([1])]), frozenset([4]): set([frozenset([6]), frozenset([7]), frozenset([3]), frozenset([1])]), frozenset([1]): set([frozenset([6]), frozenset([4]), frozenset([5]), frozenset([2]), frozenset([3])]), frozenset([2]): set([frozenset([6]), frozenset([5]), frozenset([3]), frozenset([1])])}

输出应该是一个只有两个节点的图，它们是图中所有节点的冻结集。此时它会遇到 KeyError。

def kargerMinCut(graph):
if len(graph) == 2:
    return graph
u = random.choice(graph.keys())   # u and v are frozensets, idea is that they form
v = random.choice(list(graph[u])) # a clique in a single frozenset
for node in graph:
    if node != u and node != v:
        links = graph[node]       
        if u in links or v in links:
            links.add(frozenset(tuple(u | v))) # combine u and v to form one link
            links.discard(u)                   # delete old links to u and v
            links.discard(v)            
            graph[node] = links
graph[u | v] = graph[u] | graph[v]             # new key for u and v 
del graph[u], graph[v]                         # u and v are no longer needed
return kargerMinCut(graph)
4

1 回答 1

1

我认为问题可能出在is关键字的使用上。请注意，在 python 中，is仅当两个参数引用完全相同的对象时才返回 true （相当于char* == char*C++ 中。==如果内容相同，则运算符返回 true （相当于string == stringC++ 中）。

所以与其is not尝试!=。

在 python 中遍历图形中的元素时，我曾经遇到过同样的问题。:)

PS--另外，我会把下面这行写成一个完整的if：

links.add(frozenset(tuple(u | v))) if u in links or v in links else None
于 2012-07-05T19:08:09.767 回答