0

I found this neat Kruskal's algorithm implementation, and now I would like to 'invert' it, so that it produces a maximum spanning tree instead of the minimum spanning tree. I was naïve enough to try changing if rank[root1] > rank[root2]: to if rank[root1] < rank[root2]: in union. Obviously this didn't work. I also tried swapping root1 and root2 in a few places. Apparently this code's complexity is beyond my skills. The code:

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))

How could I change the script to produce a maximum spanning tree? Even radical changes are welcome, as long as the returned graph looks like

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)
]

Thank you!

Tamataan
  • 1
  • 2
  • Presumably the answer is to implement the answers to [How to find maximum spanning tree?](//stackoverflow.com/q/4992664) – Martijn Pieters Jan 30 '18 at 11:26
  • Just use the *negative* value for the weight. – Martijn Pieters Jan 30 '18 at 11:27
  • Great, thank you for the quick answer! This was helpful. – Tamataan Jan 30 '18 at 11:29
  • I'm not sure you are implementing the algorithm correctly. You never use the weight, you only sort the edges *alphabetically*. – Martijn Pieters Jan 30 '18 at 11:31
  • Oh, good point! I'll modify that too. – Tamataan Jan 30 '18 at 11:34
  • I note your code appears to be based on https://github.com/israelst/Algorithms-Book--Python/blob/master/5-Greedy-algorithms/kruskal.py; see how the weights are listed *first*? That's important, because then you are sorting those edges by weight first. You could just *reverse* the sort then, after which using `rank[root1] < rank[root2]` will work too. – Martijn Pieters Jan 30 '18 at 11:35
  • It's fine to use a different order, but then you need to adjust your sort; use a `key=lambda edge: edge[-1], edge[:2]` to sort on weights first, then break ties by sorting on node names. – Martijn Pieters Jan 30 '18 at 11:36
  • Ok, I used `edges.sort(key=itemgetter(2), reverse=True)`, and `rank[root1] < rank[root2]`. Everything's working perfectly now. Thank you a million times, you rock! – Tamataan Jan 30 '18 at 13:35

0 Answers0