0

我发现了这个简洁的 Kruskal 算法实现，现在我想“反转”它，以便它产生最大生成树而不是最小生成树。我太天真了，试图改变if rank[root1] > rank[root2]:工会if rank[root1] < rank[root2]:。显然这没有奏效。我还尝试在几个地方交换 root1 和 root2。显然，这段代码的复杂性超出了我的技能。编码：

parent = dict()
rank = dict()

def make_set(vertice):
   parent[vertice] = vertice
   rank[vertice] = 0

def find(vertice):
   if parent[vertice] != vertice:
      parent[vertice] = find(parent[vertice])
   return parent[vertice]

def union(vertice1, vertice2):
    root1 = find(vertice1)
    root2 = find(vertice2)
    if root1 != root2:
        if rank[root1] > rank[root2]:
            parent[root2] = root1
        else:
            parent[root1] = root2
        if rank[root1] == rank[root2]: rank[root2] += 1

def kruskal(graph):
    for vertice in graph['vertices']:
        make_set(vertice)
        minimum_spanning_tree = set()
        edges = list(graph['edges'])
        edges.sort()
#print edges
    for edge in edges:
        vertice1, vertice2, weight = edge
        if find(vertice1) != find(vertice2):
            union(vertice1, vertice2)
            minimum_spanning_tree.add(edge)

    return sorted(minimum_spanning_tree)

graph = {
'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],
'edges': set([
    ('A', 'B', 7),
    ('A', 'D', 5),
    ('B', 'C', 8),
    ('B', 'D', 9),
    ('B', 'E', 7),
    ('C', 'E', 5),
    ('D', 'E', 15),
    ('D', 'F', 6),
    ('E', 'F', 8),
    ('E', 'G', 9),
    ('F', 'G', 11)
])
}

print(kruskal(graph))

如何更改脚本以生成最大生成树？只要返回的图表看起来像这样，即使是激进的更改也是受欢迎的

edges = [
    ('A', 'B', 7),
    ("A", "D", 5),
    ("B", "C", 8),
    ("B", "D", 9),
    ("B", "E", 7),
    ("C", "E", 5),
    ("D", "E", 15),
    ("D", "F", 6),
    ("E", "F", 8),
    ("E", "G", 9),
    ("F", "G", 11)
]

谢谢！

4

0 回答 0